【POJ 2970】The lazy programmer（优先队列+贪心）

本文主要是介绍【POJ 2970】The lazy programmer（优先队列+贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这题范围不会超long long全用int存就行了

贪心的话，每次把一个任务加入到队列，如果不能在指定时间完成就到前面找a最小的一个任务补偿时间，当一个任务完成时间等于0的时候这个任务就不再放回队列

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
//typedef long long LL;
const int maxn = 100005;
int n;
struct Node{int a,b;int d;Node(int a = 0,int b = 0,int d = 0):a(a),b(b),d(d){};friend bool operator <(Node p,Node q){if(p.a != q.a)return p.a < q.a;elsereturn p.d < q.d;}
}node[maxn];
bool cmp1(Node p,Node q){return p.d < q.d;
}
int main(){while(scanf("%d",&n) != EOF){for(int i = 0; i < n; i++){scanf("%d%d%d",&node[i].a,&node[i].b,&node[i].d);}sort(node,node + n,cmp1);priority_queue<Node>q;int sum = 0;double ans = 0.0;for(int i = 0; i < n; i++){q.push(node[i]);sum += node[i].b;if(sum > node[i].d){while(sum != node[i].d){Node now = q.top(); q.pop();int  need = sum - node[i].d;              //需要补偿的时间if(now.b <= need){ans += 1.0 * now.b / now.a;sum -= now.b;}else{now.b -= need;ans += 1.0 * need / now.a;sum -= need;q.push(now);}}}}printf("%.2f\n",ans);}return 0;
}

这篇关于【POJ 2970】The lazy programmer（优先队列+贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---