https://vjudge.net/problem/POJ-3045
读题后提取到一点：例如对最底层的牛来说，它的崩溃风险=所有牛的重量-(底层牛的w+s)，则w+s越大，越在底层。
注意范围lb=-INF。
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
typedef struct{
ll w, s;
ll sum;
}Node;
Node node[];
ll n, sum=;
int C(int x)
{
ll maxm = -INF, _sum=sum;
for(int i = ; i < n; i++){
ll tmp = _sum-node[i].sum;
_sum -= node[i].w;
if(tmp>x) return ;
}
return ;
}
bool cmp(const Node a, const Node b)
{
if(a.sum != b.sum)
return a.sum>b.sum;
else return a.s>b.s;
}
int main()
{
scanf("%lld", &n);
for(int i = ; i < n; i++){
scanf("%lld%lld", &node[i].w, &node[i].s);
node[i].sum = node[i].w+node[i].s;
sum += node[i].w;
}
sort(node, node+n, cmp);
ll lb=-INF, ub=INF;
while(ub-lb>){
ll mid = (lb+ub)>>;
if(C(mid)){
ub = mid;
}
else lb = mid;
}
printf("%lld\n", ub);
return ;
}