Minion Chef and Bananas Solution

 

Problem

Minion Chef likes to eat bananas a lot. There are N piles of bananas in front of Chef; for each i (1 ≤ i ≤ N), the i-th pile contains Ai bananas.

Chef's mother wants her to eat the bananas and be healthy. She has gone to the office right now and will come back in H hours. Chef would like to make sure that she can finish eating all bananas by that time.

Suppose Chef has an eating speed of K bananas per hour. Each hour, she will choose some pile of bananas. If this pile contains at least K bananas, then she will eat K bananas from it. Otherwise, she will simply eat the whole pile (and won't eat any more bananas during this hour).

Chef likes to eat slowly, but still wants to finish eating all the bananas on time. Therefore, she would like to choose the minimum K such that she is able to eat all the bananas in H hours. Help Chef find that value of K.

Input

• The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
• The first line of each test case contains two space-separated integers N and H denoting the number of piles and the number of hours after which Chef's mom will come home.
• The second line contains N space-separated integers A1, A2, ..., AN.

Output

For each test case, print a single line containing one integer — the minimum possible value of K.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 105
• N ≤ H ≤ 109
• 1 ≤ Ai ≤ 109 for each valid i

Subtasks

Subtask #1 (30 points):

• 1 ≤ N ≤ 100
• Ai ≤ 103 for each valid i

Subtask #2 (70 points): original constraints

Sample 1:

Input

Output

3
3 3
1 2 3
3 4
1 2 3
4 5
4 3 2 7

3
2
4

Explanation:

Test case $1$: Chef can choose $K = 3$ bananas per hour. This way,

• In the first hour, Chef eats the pile $1$ as the number of bananas in the pile is less than equal to $3$.
• In the second hour, Chef eats the pile $2$ as the number of bananas in the pile is less than equal to $3$.
• In the third hour, Chef eats the pile $3$ as the number of bananas in the pile is less than equal to $3$.

Chef can finish eating all the bananas in $3$ hours. It can be shown that $3$ bananas per hour is the minimum possible speed with which Chef can finish all bananas in $3$ hours.

Test case $2$: Chef can choose $K = 2$ bananas per hour. This way,

• In the first hour, Chef eats the pile $1$ as the number of bananas in the pile is less than equal to $2$.
• In the second hour, Chef eats the pile $2$ as the number of bananas in the pile is less than equal to $2$.
• In the third hour, Chef eats the $2$ bananas from pile $3$. $1$ banana is left in pile $3$.
• In the fourth hour, Chef eats the remaining banana from pile $3$ as the number of bananas in the pile is less than equal to $2$.

Chef can finish eating all the bananas in $4$ hours. It can be shown that $2$ bananas per hour is the minimum possible speed with which Chef can finish all bananas in $4$ hours.

Test case $3$: Chef can choose $K = 4$ bananas per hour. This way,

• In the first hour, Chef eats the pile $1$ as the number of bananas in the pile is less than equal to $4$.
• In the second hour, Chef eats the pile $2$ as the number of bananas in the pile is less than equal to $4$.
• In the third hour, Chef eats the pile $3$ as the number of bananas in the pile is less than equal to $4$.
• In the fourth hour, Chef eats the $4$ bananas from pile $4$. $3$ bananas are left in pile $4$.
• In the fifth hour, Chef eats the remaining bananas from pile $4$ as the number of bananas in the pile is less than equal to $4$.

Chef can finish eating all the bananas in $5$ hours. It can be shown that $4$ bananas per hour is the minimum possible speed with which Chef can finish all bananas in $5$ hours.

Program :

#include<stdio.h>

#include<stdlib.h>

int main(void)

{   

  int i,j;

  int n,t;

  long int arr[100009],s=0,temp,p,count=0,a,l,m;

  scanf("%d",&t);

  while(t--)

  {

    s=0,temp=0,count=0;

    scanf("%d%ld",&n,&p);

    for(i=0;i<n;i++)

    {

       scanf("%ld",&arr[i]);

       s=s+arr[i];

       if(arr[i]>count)

       count=arr[i];

    }

    

    a=s/p;

    l=count;

    while(a<l)

    {  

      m=(a+l)/2;

      temp=0;

      for(j=0;j<n;j++)

      {  

         temp=temp+arr[j]/m+(arr[j]%m!=0?1:0);

       }

       if (temp>p)

       a=m+1;

       else if(temp<=p)

       l=m;

    }

    printf("%ld\n",(a+l)/2);

  }

  return 0;

}