有N个任务需要执行，第i个任务计算时占R[i]个空间，而后会释放一部分，最后储存计算结果需要占据O[i]个空间（O[i] < R[i]）。例如：执行需要5个空间，最后储存需要2个空间。给出N个任务执行和存储所需的空间，问执行所有任务最少需要多少空间。
输入 第1行：1个数N，表示任务的数量。（2 <= N <= 100000) 第2 - N + 1行：每行2个数R[i]和O[i]，分别为执行所需的空间和存储所需的空间。(1 <= O[i] < R[i] <= 10000) 输出 输出执行所有任务所需要的最少空间。 输入示例 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
按照释放的空间从大到小排序，其实仔细想想，释放的空间越大后面的任务能新开辟的空间也就越小
#include<cstdio> #include<algorithm> using namespace std; struct node { int r;//运行需要的空间 int o;//储存空间 }arr[100000+11]; bool cmp(node a,node b) { return a.r-a.o>b.r-b.o; } int main() { int n; scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d%d",&arr[i].r,&arr[i].o); sort(arr,arr+n,cmp); int sum=0,ans=0;//sum代表总空间，ans代表剩余的空间 for(int i=0;i<n;++i) { if(arr[i].r>ans)//大于剩余的空间 { int b=sum-ans;//已经被占用的空间 sum=sum+arr[i].r-ans;//总共需要的空间 ans=sum-b-arr[i].o;//当前的空闲空间 } else//小于剩余空间 { ans=ans-arr[i].o; } } printf("%d\n",sum); return 0; }
