http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3778

哎。。比赛时这题都没做出来,其实yy一下就想出来了。

拿A={8,8,10,10},M=3来说,首先把第一个菜分两个步骤出来加到第二个菜上,这样可以用10分钟完成10*3个步骤。
在此基础上,稍微变换下步骤便可以用2分钟完成剩下6个步骤:
把第3,4道菜各空出不同的2分钟出来(这样需要12分钟才能做完第3,4道菜),用来和第一道菜的前4个步骤同时做,用时4分钟。第一道菜的后两个步骤在11~12分钟完成。

照这个思路想,无论各个菜有多少步骤,答案就是

/*90ms,272KB*/

int main()
{
    int T, n, m, i, x, maxx, sum;
    SI(T);
    while (T--)
    {
        SII(n, m);
        maxx = sum = 0;
        For(i, n)
        {
            scanf("%d", &x);
            sum += x;
            maxx = max(maxx, x);
        }
        if (sum % m == 0) sum /= m;
        else sum = sum / m + 1;
        PI(max(sum, maxx));
    }
    return 0;
}

Comments

comments powered by Disqus