pascal堆积木

小MSH拥有N块积木，每块积木都有一个重量W和一个稳定值S，小MSH准备把这N块积木堆成一座高塔，她当然希望这座塔越稳定越好。对于每块积木，我们把在它上面积木的重量之和（不包括它本身）减去它的稳定值作为一个稳定分数（显然这个稳定分数越小越好），我们需要找到一种堆法，使得所有稳定分数中最大的那个最小，也就是找到一种最稳定的堆法。
输入

第一行，一个整数N(1 <= N <= 50,000)。
接下来N行，每行两个整数W(1 <= W <= 10,000)，S(1 <= S_i <= 1,000,000,000)，分别表示这块积木的重量和稳定值。
输出
输出仅一个整数，最小的稳定分数。
样例 input
3
10 3
2 5
3 3
output
2

要解题思路！！！！！！！

简单的贪心法，做法是将以（重量+稳定值）为关键字把木块信息从小到大排序，然后依次模拟从上到下堆木块，每堆一个就算出来分数，取最大的分数就可以了，O(NlogN)的算法。
具体一点：假如现在的积木从上到下序号为1~N是如上排好序摆上去的，且木块n的分数是SumW(1~n-1) - S[n]，简写为f[n] = Sum[n-1]-S[n]。
然后是重点：现在假设最大的分数是f[j]，证明命题：有更优的方案。如果有的话，一定可以通过交换木块i（i = j-1）和木块j的位置来使f[j]变小，（i不一定取值为j-1但是 i < j是一定的，然而任意i < j都可以通过i = j-1多步转化过去，所以姑且取值i = j-1），但是这是有代价的，那就是交换后f[i] = Sum[i-1] + W[j] - S[i]，交换前f[j] = Sum[i-1] + W[i] - S[j]，只要能使f[i] < f[j] 那交换就是成功的产生了更优的方案，但是f[i] < f[j] 就意味着 W[j] - S[i] < W[i] - S[j] 也就是说 W[j]+S[j] < W[i]+S[i]，这个与原先的排序是矛盾的，所以命题不成立，没有更优方案。

我是来看评论的

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息