一、思路

本题使用二分搜素，可以使用一个简单的思路解决，二分的mid为牛组成的序列的最大的危险值。

解题目的核心是二分的judge算法，我们能够知道，最底下的一头牛，所承担的危险值为，所有牛承担的危险值减去它的质量再减去它的力量。同时二分传递的mid为序列中最大的风险值，那么对于最底下的那头牛，可以推出如下的表达式

所有牛的质量-最底下的牛的质量-最底下的牛的力量=最底下的牛的风险值<=mid

所有牛的质量-最底下的牛的质量-最底下的牛的力量<=mid

所有牛的质量-mid<=最底下的牛的质量+最底下的牛的力量

那么我们先根据（牛的质量+牛的力量）进行升序排序，用lowerBound找到满足条件的牛，这些就是可以放在最底下的牛，然后对于下一头牛，需要满足的规则为

所有牛的质量-以选择的牛的质量和-该的牛的质量-该的牛的力量=该牛的风险值<=mid

所有牛的质量-以选择的牛的质量和-该的牛的质量-该的牛的力量<=mid

所有牛的质量-以选择的牛的质量和-mid<=该的牛的质量+该的牛的力量

那么不难看出，我们要尽最大可能维护这个表达式可行时，一定要先选择那些质量大的牛，所以我们每一次用lower_bound找到满足条件的所有牛之后，都通过优先队列，选择质量最大的牛，然后记录count++用总质量减去已选择的质量再次进行判断。（这里注意优先队列的值不要放重复了）

最后count==N，那么就代表mid可行，同时我们需要把数字第N+1个位置放置无穷大，如果找到了第N+1个位置，或者满足条件的牛都用过了（优先队列为空），那么就证明mid过小。

二、代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Cow
{
    ll weight, strength;
    Cow(ll weight = 0, ll strength = 0) : weight(weight), strength(strength) {}
};
Cow cows[50007];
int N;
ll inf = 0x3f3f3f3f3f3f3f3f, cowWeightSum = 0;
bool compare(const Cow &a, const Cow &b)
{
    return (a.weight + a.strength) < (b.weight + b.strength);
}
bool operator<(const Cow &a, const Cow &b)
{
    return a.weight < b.weight;
}
void input()
{
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld%lld", &cows[i].weight, &cows[i].strength);
        cowWeightSum += cows[i].weight;
    }
    cows[N].weight = inf;
    cows[N].strength = inf;
    sort(cows, cows + N + 1, compare);
}
bool judge(ll mid)
{
    ll currentWeightSum = cowWeightSum - mid;
    priority_queue<Cow> que;
    int count = 0;
    int limit = N;
    while (count < N)
    {
        int next = lower_bound(cows, cows + N + 1, currentWeightSum, compare) - cows;
        if (next == N)
        {
            return false;
        }
        for (int i = next; i < limit; i++)
        {
            que.push(cows[i]);
        }
        limit = min(next, limit);
        if (que.empty())
        {
            return false;
        }
        Cow cow = que.top();
        que.pop();
        currentWeightSum -= cow.weight;
        count++;
    }
    return true;
}
void binarySearch()
{
    ll left = -1000000001, right = 500000000;
    while (left + 1 < right)
    {
        ll mid = (left + right) / 2;
        if (judge(mid))
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    printf("%lld\n", right);
}
int main()
{
    input();
    binarySearch();
    return 0;
}