假设现在的排列顺序是1~n，且最大的risk出现在位置i处 那么 M a x R i s k 1 = ∑ j = 1 i − 2 p [ j ] . w + p [ i − 1 ] . w − p [ i ] . s MaxRisk_1=\sum_{j=1}^{i-2}p[j].w+p[i-1].w-p[i].s MaxRisk1=∑j=1i−2p[j].w+p[i−1].w−p[i].s 假设交换第i项和第i-1项， M a x R i s k MaxRisk MaxRisk变大，即变得“不优” 此时 M a x R i s k 2 = ∑ j = 1 i − 2 p [ j ] . w + p [ i ] . w − p [ i − 1 ] . s MaxRisk_2=\sum_{j=1}^{i-2}p[j].w+p[i].w-p[i-1].s MaxRisk2=∑j=1i−2p[j].w+p[i].w−p[i−1].s
显然， M a x R i s k 1 ≤ M a x R i s k 2 MaxRisk_1\leq MaxRisk_2 MaxRisk1≤MaxRisk2 ⟺ \iff ⟺ p [ i − 1 ] . w − p [ i ] . s ≤ p [ i ] . w − p [ i − 1 ] . s p[i-1].w-p[i].s\leq p[i].w-p[i-1].s p[i−1].w−p[i].s≤p[i].w−p[i−1].s ⟺ \iff ⟺ p [ i − 1 ] . w + p [ i − 1 ] . s ≤ p [ i ] . w + p [ i ] . s p[i-1].w+p[i-1].s\leq p[i].w+p[i].s p[i−1].w+p[i−1].s≤p[i].w+p[i].s 故得出结论，两者加和小的需要放在前面
代码:
const int maxn=2e6+7; const int INF=0x3f3f3f3f; const ll INFF=1e18; struct node { ll w,s; }p[maxn]; int n; ll sum=0,maxx=-INFF; bool cmp(node a,node b){return a.w+a.s<b.w+b.s;} int main() { scanf("%d",&n); rep(i,1,n)scanf("%lld%lld",&p[i].w,&p[i].s); sort(p+1,p+1+n,cmp); rep(i,1,n) { maxx=max(maxx,sum-p[i].s); sum+=p[i].w; } WW(maxx); return 0; }