1217 - 小明和他的同学们


对于10%的数据,1<= n<= 4; 对于100%的数据,1<= n<=100,1<=m<=5000,1<=x<=1000,1<=t<=20,1<=每个同学吃一块巧克力的时间<=1000。

题目里面描述 n 个同学是一起开始吃巧克力的,吃完一个随即就去吃剩下的,那么这就可以用优先队列模拟 n 个同学吃巧克力的过程,每次取出吃最快的那个同学,之后把当前巧克力给他。

同时吃完优先分给更快的同学。终止条件为吃完 m 个巧克力或者每个同学都用时都大于等于 x ,最后在统计一下每个同学最后吃的那个巧克力是否吃完即可,时间复杂度 O(t×mlogn) 。

需要注意的是,本题不用优先队列并没有很好的解法,看起来似乎可以用 x/ti来计算每个同学吃的数量( ti 为同学 i 吃巧克力所用的时间),但我们思考,可能在他能够拿到最后一块巧克力之前,所有巧克力已经被分完了,并且这些被分掉的巧克力,未必都能够吃完。