感觉其他dalao讲的不是很明白啊,我这样的蒟蒻看不懂啊.
在luogu这个dalao遍地的地方我蒟蒻看个题解也不明白,我为跟我同病相怜的蒟蒻写一篇吧
其实真是不太明白,大部分题解都是只说
体重大的在下面
力量大的在下面
(和)
没有证明啊....
设wa + sa > wb + sb且a与b相邻
a在上面,b在下面时
那么a和b上面的牛总重为w
a的压扁指数为w - sa
b为w + wa - sb
因为wa + sa > wb + sb
那么wa - sb > wb - sa
因为wb >= 0,所以wa - sb > - sa
所以w + (wa - sb) > w - (sa),所以当a在上时,总压扁指数为w + wa - sb(不考虑上面的牛的压扁指数)
b在上面,a在下面时
a -> w + wb - sa
b -> w - sb
因为wa + sa > wb + sb
所以wb - sa < wa - sb
又因为wa > 0
所以wb - sa < -sb
所以w + (wb - sa) < w + (-sb),所以当b在上时,总压扁指数为w - sb(不考虑上面的牛的压扁指数)
综上
当a在上时w + wa - sb
b在上时 w - sb
所以力量加体重大(w + s 大)的在下面比在上面更优
如果考虑上面的牛的话.
若上面牛的总压扁指数比a和b的大,那么交换了也不会变差(即无所谓).
如果不如a和b的大的话,就成了我说的这种情况
#include<bits/stdc++.h>
#define AC 0
using namespace std;
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
struct po
{
int w,s;
};
po a[50001];
bool cmp(po a,po b){
return a.w + a.s < b.w + b.s;
}
int main(int argc, char const *argv[])
{
int n;
cin>>n;
for(int i = 1;i <= n;++i){
a[i].w = read();
a[i].s = read();
}
sort(a + 1,a + 1 + n,cmp);//贪心排序
int tot = 0,ans = -99999999;//一个数减另一个数,不排除负数的可能,ans要弄负值
for(int i = 1;i <= n;++i){
ans = max(ans,tot - a[i].s);
tot += a[i].w;
}
cout<<ans<<endl;
return AC;
}
给像我一样的蒟蒻的题解,dalao勿喷