博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
51nod 1099 任务执行顺序(贪心)
阅读量:630 次
发布时间:2019-03-14

本文共 584 字,大约阅读时间需要 1 分钟。

51nod 1099 任务执行顺序(贪心)

使数组按照(o-r)大小来排序就好,在算第i个数的最大值时,前i-1个数决定了其初始值sum,那么将(o-r)越小的放在后面越优

#include
using namespace std;const int N = 1e6+10;struct Node{ int o,r,c;}a[N];bool cmp(Node a,Node b){ return a.c > b.c;}int main(){ int n; scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%d%d",&a[i].o,&a[i].r); a[i].c = a[i].o-a[i].r; } sort(a,a+n,cmp); int maxn = 0, sum = 0; for(int i = 0; i < n; i++) { maxn = max(maxn, sum+a[i].o); sum += a[i].r; maxn = max(maxn, sum); } printf("%d\n",maxn); return 0;}

转载地址:http://gfaoz.baihongyu.com/

你可能感兴趣的文章