[文章目录]
Description
给你n头牛，每个牛有一个力量和一个体重，他们玩叠罗汉，牛的危险值等于它上面所有牛的体重之和-自身力量。n<=50000
感性理解：体重大的往下放，力量大的也往下放。所以按和排序。
其实可以证明一下，考虑交换两头牛，发现并不比原来的解优。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n;
struct node
{
int a,b;
}a[51000];
bool cmp(node x,node y) {return x.a+x.b<y.a+y.b;}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].a,&a[i].b);
sort(a+1,a+n+1,cmp);
ll mx=-1000000000,sum=0;
for(int i=1;i<=n;i++)
{
mx=max(mx,sum-a[i].b);
sum+=a[i].a;
}
printf("%lld",mx);
return 0;
}