首页 > 代码库 > Uva 1153 Keep the Customer Satisfied (贪心+优先队列)
Uva 1153 Keep the Customer Satisfied (贪心+优先队列)
题意:已知有n个工作,已知每个工作需要的工作时间qi和截至时间di,工作只能串行完成,问最多能完成多少个工作
思路:首先我们按照截至时间从小到大排序,让它们依次进入优先队列中,当发生执行完成时间大于截至时间时,我通过优先队列把工作中最长的需要时间出队
优先队列的比较函数:
struct cp { bool operator () (node a,node b) { //可以理解为我如何让后入队的优先出队 if(b.need>a.need) return true; else return false; } };
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn=800005; struct node { int need,ed; }data[maxn]; struct cp { bool operator () (node a,node b) { if(b.need>a.need) return true; else return false; } }; bool cmp(node a,node b) { if(a.ed<b.ed) return true; else if(a.ed==b.ed) { if(a.need<b.need) return true; else return false; } else return false; } int main() { int n; int t; cin>>t; while(t--) { cin>>n; for(int i=0;i<n;i++) { cin>>data[i].need>>data[i].ed; } sort(data,data+n,cmp); priority_queue<node,vector<node>,cp> q; int tmp=0,ans=0; for(int i=0;i<n;i++) { q.push(data[i]); tmp=tmp+data[i].need; if(tmp>data[i].ed) { node k=q.top(); q.pop(); tmp=tmp-k.need; ans--; } ans++; } if(ans<=0) ans=0; cout<<ans<<endl; if(t) cout<<endl; } return 0; }
Uva 1153 Keep the Customer Satisfied (贪心+优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。