https://www.51nod.com/tutorial/course.html#!courseId=23

题目大意：有$N$个任务需要执行，第$i$个任务计算时占$R[i]$个空间，而后会释放一部分，最后储存计算结果需要占据$O[i]$个空间$(O[i] < R[i])$。

解题关键：按照$b[i]$不增的顺序排序，是最“有利”的。

一定注意：输入的不是a,b，而是O与R，比较的是b，两者的差的绝对值

结论：

如果对于$b[0] >  = b[1] >  =  \ldots  >  = b[x] < b[x + 1]$
$\left( {a[0],b[0]} \right) \ldots .\left( {a[x],{\rm{ }}b[x]} \right){\rm{ }}\left( {a[x + 1],{\rm{ }}b[x + 1]} \right)$的组合可以不产生负数，则我们交换$b[x]$和$b[x+1]$也可以不产生负数。

证明：
交换$(a[x],b[x])$和$(a[x + 1],b[x + 1])$对$x+1$更有利了，因为每个括号实际上是一个负数，所以越早安排这个括号，被减数就越大，就越不容易形成负数。

关键看$(a[x],b[x])$移动到后面会不会产生负数。

那其实是看之前的结果$ - a[x + 1] + b[x + 1] - a[x]$会不会产生负数，（注意$ - a[x + 1] + b[x + 1]$不会产生负数，因为我们刚才已经证明了，对$x + 1$更有利）

而我们知道之前的结果$-a[x] + b[x] – a[x + 1]$不会产生负数（因为我们的假设就是这样），而$b[x + 1] > b[x]$，所以前者更大，所以$-a[x + 1] + b[x + 1] – a[x]$不会产生负数。

因此我们证明了交换之后仍然不产生负数，也就是原先不产生负数，我们交换后仍然不产生负数。

而经过若干次这样的交换之后，我们肯定会把序列交换成按照b的不增顺序排序的。从而我们证明了，任何可行的方案都不好于按照b不增顺序排序的序列执行的方案，从而证明了我们的贪心策略是有效的。

 1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 struct node{ 5     int a,b; 6 }c[100002]; 7 bool cmp(node x,node y){ 8     return x.a-x.b>y.a-y.b; 9 }10 int main(){11     int n;12     cin>>n;13     for(int i=0;i<n;i++)    cin>>c[i].a>>c[i].b;14     sort(c,c+n,cmp);15     int sum=c[0].a,tt=0;16     for(int i=0;i<n;i++){17         if(tt+c[i].a>sum) sum=tt+c[i].a;18         tt+=c[i].b;19     }20     printf("%d",sum);21     return 0;22 }

[贪心]任务执行顺序