原题见这里
少女杨超越(因为看到幸运值,我就想起了她,原文人物是Lena)在准备参加多项考试。她的幸运值初始是0,并且她坚信要攒好运。
第i项考试有两个关联的值,L[i]和T[i]。
- L[i]是对应的幸运值。如果杨超越通过了此考试,那么幸运值会减少L[i],相反,如果挂了,幸运值会增加L[i]。emmmm这就是考试看人品啊。
- T[i]表示此考试的重要程度,1表示重要,0表示不重要。
限制超越妹妹最多能挂掉k项重要的考试,问完成全部考试后,她可能拥有的最大幸运值是多少?
这个题目就是单刀直入型的解法了,假设重要的考试一共有n项,如果n > k, 则从中选择幸运值最大的k项来挂,否则全部挂掉即可。不重要的考试可以全挂。
我这里是反过来处理的,先算出有多少必须及格的项数winNum,然后从重要的考试中选择幸运值最小的winNum项通过,剩余的全挂即可。
具体代码见solve.php