[ exttt{Description}
]
有 (n) 头牛，每头牛都有自己的体重 (W_i) 和力量 (S_i) 。
将这 (n) 头牛摞在一起，每头牛的压扁指数定义为：压在该牛上面的牛的体重之和 (-) 该牛力量 。
您需要找到一种摞牛方案，使得压扁指数最大的牛的压扁指数最小。
求这个压扁指数。
[ exttt{Solution}
]
- 微扰（邻项交换）证明贪心好题。
- 考虑任意一个摞牛方案，设该摞牛方案中，从顶端往底端数的第 (i) 头牛的体重为 (W_i) ，力量为 (S_i) 。
- 记 (Z_i=sumlimits_{j=1}limits^{i}W_j)（前 (i) 头牛体重和）。
- 我们考虑任意一个邻项，考虑交换，易得：
交换前第 (i) 头牛的压扁指数：(Z_{i-1}-S_i) 。
交换前第 (i+1) 头牛的压扁指数：(Z_{i-1}+W_i-S_{i+1}) 。
交换后第 (i) 头牛的压扁指数：(Z_{i-1}-S_{i+1}) 。
交换后第 (i+1) 头牛的压扁指数：(Z_{i-1}+W_{i+1}-S_i) 。
- 我们发现需要比较这两个式子的值：
[max(Z_{i-1}-S_i,Z_{i-1}+W_i-S_{i+1}) \ max(Z_{i-1}-S_{i+1},Z_{i-1}+W_{i+1}-S_i)
]
- 式子内部减去 (Z_{i-1}) ，得：
[max(-S_i,W_i-S_{i+1}) \ max(-S_{i+1},W_{i+1}-S_i)
]
- 式子内部加上 (S_i+S_{i+1}) ，得：
[max(S_{i+1},W_i+S_i) \ max(S_i,W_{i+1}+S_{i+1})
]
- 注意到 (W) 为正整数，所以有 (S_i leq W_i+S_i) ，(S_{i+1} leq W_{i+1}+S_{i+1}) 。
- 也就是说当 (S_{i+1} = max(S_{i+1},W_i+S_i)) 时，也定不会比 (max(S_i,W_{i+1}+S_{i+1})) 大，另一式子同理。
- 故可以转化为比较这两个式子的值：
[W_i+S_i \ W_{i+1}+S_{i+1}
]
- 当 (W_i+S_i leq W_{i+1}+S_{i+1}) 时，上式 (leq) 下式，则交换前定不比交换后优。
- 当 (W_i+S_i geq W_{i+1}+S_{i+1}) 时，上式 (geq) 下式，则交换后定不比交换前劣。
- 我们将满足 (W_i+S_i > W_j+S_j) ，(i<j) 的点对 ((i,j)) 视为一个逆序对，显然，在任意局面下，增加逆序对的数量都不会使整体结果变优，减少逆序对的数量都不会使整体结果变差。
- 根据冒泡排序，在任意局面下，都可通过邻项交换使得该序列的逆序对数量变 (0) 。
- 也就是说，即使你的最优摞牛方案逆序对数量不为 (0) ，我也可以通过排序，使得在答案不更劣的情况下，使得逆序对数量为 (0) ，故逆序对为 (0) 时一定为最优方案。
- 当逆序对数量为 (0) 时，实际上就是将这 (n) 头牛以 (W_i+S_i) 为关键字从小到大排序。
- 至此我们就有一个贪心策略：将这 (n) 头牛以 (W_i+S_i) 为关键字从小到大排序。
尽管这个贪心策略很玄学。 - 排好序，按题目描述说的一样算出答案即可。
- (mathcal{O(n log n)}) 。
[ exttt{Code}
]
#include<cstdio>
#include<algorithm>
#define RI register int
using namespace std;
inline int read()
{
int x=0,f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-f;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
const int N=50010;
int n;
struct Cow{
int W,S;
}a[N];
bool cmp(Cow a,Cow b)
{
return a.W+a.S<b.W+b.S;
}
long long ans=-0x3f3f3f3f;
int main()
{
n=read();
for(RI i=1;i<=n;i++)
a[i].W=read(),a[i].S=read();
sort(a+1,a+1+n,cmp);
long long sum=0;
for(RI i=1;i<=n;i++)
{
ans=max(ans,sum-a[i].S);
sum+=a[i].W;
}
printf("%lld
",ans);
return 0;
}
[ exttt{Thanks} exttt{for} exttt{watching}
]