2012-0050

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

假设选了前K个人给Gift Cola， 那么:
{{{
Ans = ∑(1,k)Q[i] + ∑(k+1,n)P[i] - k*m
    = ∑(1,k)Q[i] - ∑(1,k)P[i] - k*m + ∑(1,n)P[i]
    = ∑(1,k)(Q[i]-P[i]-m) + ∑(1,n)P[i]
}}}
可知，当 Q[i]-P[i]-m > 0时，ans会增长，满足单调性，那么按Q[i]-P[i]排序后，二分出k即可。

by FJYsmall

假设选了前K个人给Gift Cola， 那么:

Ans = ∑(1,k)Q[i] + ∑(k+1,n)P[i] - k*m
    = ∑(1,k)Q[i] - ∑(1,k)P[i] - k*m + ∑(1,n)P[i]
    = ∑(1,k)(Q[i]-P[i]-m) + ∑(1,n)P[i]

可知，当 Q[i]-P[i]-m > 0时，ans会增长，满足单调性，那么按Q[i]-P[i]排序后，二分出k即可。

by FJYsmall