题面

有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。
例如：执行需要5个空间，最后储存需要2个空间。给出N个任务执行和存储所需的空间，问执行所有任务最少需要多少空间。

输入样例

20
14 1
2 1
11 3
20 4
7 5
6 5
20 7
19 8
9 4
20 10
18 11
12 6
13 12
14 9
15 2
16 15
17 15
19 13
20 2
20 1

输出样例

135

AC代码

#include <bits/stdc++.h>
using namespace std;
int n, cnt, mi=1e9, ma;
struct KKK{
    int r, o;
}a[100005];
int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &a[i].r, &a[i].o);
        cnt+=a[i].o;
        mi=min(mi, a[i].r-a[i].o);
    }
    printf("%d", cnt+mi);
    return 0;
}

正解思路(摘自网络

这个题目最重要的是确定贪心策略，每个任务执行需要R的空间，储存需要O的空间，他俩的差值不妨设为B，这个问题这一开始也不大理解，需要多少空间？应该怎样安排都差不多吧，其实不然。你可以自己随便写两三组数，随意按不同的顺序尝试下，结果是不一样的。为什么呢？因为他会释放空间，这又要考虑内存资源的占有问题，

假设所有的任务满足 R== O ，那么最优解就是O之和。然而事实是 R > O ，那么每次一执行某个任务，

就会先多调用 R - O的空间。如图：灰黑色条代表执行时占用的空间，黄色代表执行完后存储空间。

实际上，每次释放的R-O的大小，就是总是在多占用内存的部分，

所以我们以R-O按从大到小排序，用所有O相加在减少R-O的最小值，就是最优策略。

求助

关于正解有一个疑惑，假设有一个任务R极大，O极小，R的大小大于所有O的和加R-O的最小值（也就是用正解方法算出来的答案）的话正解答案不就不对了吗？？？我看了很多题解好像都没有考虑这样的问题，求助一下为什么不用考虑这种情况