bzoj1629[Usaco2007 Demo]Cow Acrobats

分析：这题我一看最大值最小，秒二分，然而判断想了一节课没想出来。。 然后觉得二分不可做那就贪心？可是这个按照乘除法之类的性价比好像不符合啊，随便举一个反例都有。然后脑子里有一瞬间想过是不是可能加减？但是立马排除了。。

结果tm题解就是按照和排序以后直接做，woc那你给个50000的范围？你开到100000，200000都可以的啊。。至于为什么，hzwer的解释是对于相邻的两个如果最优，那么肯定全局最优。。

#include<cstdio> #include<cstring> #include<algorithm> #include<math.h> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; typedef long long ll; const int inf=1e9+5; int n,m; const int N=1e5+5; struct node { int w,s; }a[N]; bool cmp(node x,node y) { return x.w+x.s<y.w+y.s; } int main() { scanf("%d",&n); fo(i,1,n)scanf("%d%d",&a[i].w,&a[i].s); sort(a+1,a+1+n,cmp); ll sum=0,ans=-inf; fo(i,1,n) { //printf("%d\n",sum); ans=max(ans,sum-a[i].s); sum+=a[i].w; } printf("%lld\n",ans); return 0; }