题目描述

农民约翰的N头奶牛（编号为1..N）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这N头奶牛中的每一头都有着自己的重量Wi以及自己的强壮程度Si。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数N，表示奶牛数量。

接下来N行，每行输入两个整数，表示牛的重量和强壮程度，第i行表示第i头牛的重量Wi以及它的强壮程度Si。

输出格式

输出一个整数，表示最大风险值的最小可能值。

数据范围

$1≤N≤50000,$
$1≤Wi≤10,000,$
$1≤Si≤1,000,000,000$

输入样例：

3
10 3
2 5
3 3

输出样例：

2

算法一：贪心

贪心策略：将所有牛按$w_i+s_i$升序排列，值小的放在上面

证明：

1. 贪心得到的答案>=最优解（根据最优解定义：所有方案中最小的）
2. 贪心所得的答案<=最优解

假设第$i$头牛和第$i+1$头牛不是按升序排列，交换其顺序后不会改变其他牛的危险值

同时消去$w_1 + w_2 + …+w_{i - 1}$不影响结果

同时加上$s_i + s_{i + 1}$

由$w_i + s_i > w_{i + 1} + s_{i + 1}$且$w_{i + 1} > 0$

故$w_i+s_i>s_{i+1}$即$w_i+s_i=max(s_{i+1},w_i+s_i)$

又因为$w_i+s_i>s_i$且$w_i+s_i>w_{i+1}+s_{i+1}$

故$max(s_{i+1},w_i+s_i)>max(s_i,w_{i+1}+s_{i+1})$

故交换之后两头牛的危险系数最大值降低

因此对于所有逆序的排列都可按此种交换将危险系数降低

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010;

int n;
PII a[N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        int w, s;
        scanf("%d%d", &w, &s);
        a[i].first = w + s;
        a[i].second = s;
    }

    sort(a, a + n);

    int res = -2e9, sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        res = max(res, sum - a[i].second);
        sum += a[i].first - a[i].second;
    }

    cout << res << endl;

    return 0;
}