传送门
解题思路
设 \(i,j\) 相邻,前面的重量和为 \(x\)。
若 \(i\) 在上面更优,则
\(x-s[i]\) 一定小于 \(x+w[j]-s[i]\),
\(x-s[j]\) 一定小于 \(x+w[i]-s[j]\),
所以上述式子可以化简为:
即
\[w[i]+s[i]<w[j]+s[j] \]所以按照 \(w+s\) 升序排序即可。
AC代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include<stack>
#include<set>
#include<bitset>
#include<cstdio>
#include<ctime>
using namespace std;
const int maxn=5e4+5;
int n;
long long ans=-1e9,now;
struct node{
int a,b;
}x[maxn];
bool cmp(node a ,node b){
return a.a+a.b<b.a+b.b;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;++i){
cin>>x[i].a>>x[i].b;
}
sort(x+1,x+n+1,cmp);
for(int i=1;i<=n;i++){
ans=max(ans,now-x[i].b);
now+=x[i].a;
}
cout<<ans;
return 0;
}