51nod 1099 任务执行顺序 神奇的贪心

1099 任务执行顺序

1. 1.0 秒
2.  
3. 131,072.0 KB
4.  
5. 20 分
6.  
7. 3级题

有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

分析：

答案 = 要占用的空间（O[i]的前缀和） + 最小运行时净占用

所以要保证最小运行是净占用最小

最小运行时净占用 = min(R[i] - O[i])

按照这个排序即可

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL inf=1e18;
const int N = 5000050;
int n,m;
struct Node
{LL r,o;
} a[N];
bool cmp(Node x,Node y)
{	return x.r-x.o>y.r-y.o;
}
int main()
{LL  ans=0;scanf("%d",&n);for(int i=1; i<=n; i++){scanf("%lld%lld",&a[i].r,&a[i].o);;}sort(a+1,a+n+1,cmp);LL maxx=0;for(int i=1;i<=n;i++){//cout<<a[i].r<<"   "<<a[i].o<<" "<<ans<<endl;maxx=max(maxx,ans+a[i].r);ans+=a[i].o;}cout<<max(ans,maxx)<<endl;return 0;
}