1 条题解
-
0
何老师 (root) LV 0 MOD @ 2024-05-07 12:33:41
贪心:
1、模拟贪心过程:用一个大根堆,当堆中元素个数大于m时,从堆中选出前m个自减1,Ans++,然后不为0的再次进堆。重复上面过程,直到堆中元素小于等于m个为止,最后答案为Ans加对顶元素。2、规律:
当n不大于m时,显然Ans=max{ x[i] | 1<=i<=n }
当n大于m时,除最后一分钟,前面每分钟都可以找到m道菜,而最后一分钟做剩下的菜.即:
令sum=x[1]+x[2]+...x[n];
t=sum/m+(sum%m>0)
最后答案: Ans=max(max{ x[i] | 1<=i<=n }, t);
- 1