111qqz的小窝

老年咸鱼冲锋!

codeforces #339 div2 D

http://codeforces.com/contest/613/problem/B
题意:有n个技能,初始每个技能的level为a[i],每个技能最大level为A(不妨称为满级技能),设满级技能个数为maxnum,最小的技能level为minval,问如何将m个技能点分配到n个技能上使得cf*maxsum+cm*minval (n<=1E5,a[i],A<=1E9,cf,cm<=1E3,m<=1E15)

思路:贪心。如果让有限的maxsum个技能满级的话,那么一定是让初始最大的maxsum技能满级更优。我们O(n)可以预处理一个c[i]数组,表示将i个技能变成最大值的最小花费。

然后再预处理一个前缀和数组,sum[i]表示初始最小的i个的技能的花费之和。

然后从0到n枚举变成最大值的技能的个数,在剩下的技能中二分能达到的最小值。

注意要按照原来顺序输出,所以记得记录id.

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz