游客 Signup | Login
中文 | En

3538 - 迅速烹饪

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 128 MB

小明出身新东方，所以对于烹饪他可是很在行的。

可是他的数学不怎么好。

今晚他想在家做顿丰盛的晚餐招待他的女盆友，为什么呢？因为他想向女友
炫耀下他的烹饪技能。 

<span style="font-family:NSimSun;font-size:18px;"><strong>所以捏，小明决定准备n道菜，第i个菜含有Ai个的步骤。</strong></span><br />

菜应该按步骤顺序完成，在烹饪的每一分钟，小明最多可以选择M道不同的菜肴and完成选择菜的一个步骤。
教练高想知道他需要准备晚餐最少的时间。你来帮他计算咯~o(∩_∩)o

Input

有多组测试数据，先输入T,表示有T组测试数据。

然后给出两个整数 N and M (1 <= N, M <= 40000). 接下来是N 个整数 Ai (1 <= Ai <= 40000).

Output

对于每组数据都只输出一行，即完成所有菜的最少时间。

Examples

Input Format

2
3 2
2 2 2
10 6
1 2 3 4 5 6 7 8 9 10

Output Format

3
10

Solution C

#include<stdio.h>
int x[50000];
int main()
{
    int n,sum,time;
    
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        sum=0;
        scanf("%d%d",&a,&b);
        int i,j;
        for(i=0; i<a; i++)
        {
            scanf("%d",&x[i]);
            sum+=x[i];
        }
        int max=0;
        for(i=0;i<a;i++)
            if(max<x[i])
            max=x[i];
        if(b>=a)
            printf("%d\n",max);
        else
        {
            if(sum%b==0)
                time=sum/b;
            else
                time=sum/b+1;
            if(time<max)
               time=max;
            printf("%d\n",time);
        }

    }
       return 0;
}
请先登陆