题意:
给出n,k.n门课程,第i门的课程的学分是s[i],分数是c[i]
删除最多k门课程使得$\frac{\sum s[i]c[i]}{\sum s[i]}$最大
问这个最大值是多少
解法:
改一下式子 $\frac{\sum s[i]c[i] \times x[i]}{\sum s[i]}$(x[i]代表0或1,最多k个0)
随便猜测一个值L
1.存在一组解,使得$\sum(s[i]c[i] - L \times c[i]) \times x[i] \geq 0$
变形得
$\sum s[i]c[i] \times x[i] \geq L \sum \times c[i] \times x[i] $
$\frac{\sum s[i]c[i] \times x[i]}{\sum s[i]} \geq L$
那么L比要求的最大值小或者相等
2.对于任意解,使得$\sum(s[i]c[i] - L \times c[i]) \times x[i] < 0$
同理
$\frac{\sum s[i]c[i] \times x[i]}{\sum s[i]} < L$
即L比要求的最大值大
那么这就能二分答案(也就是二分L)
代码
1 |
|
参考资料:
算法竞赛进阶指南 P185