首页 > 代码库 > UVa1153 Keep the Customer Satisfied (贪心,优先队列)
UVa1153 Keep the Customer Satisfied (贪心,优先队列)
链接:http://bak.vjudge.net/problem/UVA-1153
分析:将n个工作按截止时间d从小到大排序。用优先队列维护在当前截止时间di下,实现完成工作数的最大化时,选取的各个工作的需要时间。每次取一个工作i,先把它扔进队列中(这样保证n个工作都进过队列,在后面我们只需记录下从队列里删除的工作总数ans),计算得到cost(在截止时间di-1之前完成最大工作数所耗用的总时间)加上di的总耗时,如若超过了当前截止时间di,那么根据贪心的思想,从队列里删除一个最费时的工作ans++,同时要注意把删除掉的工作的耗时从总耗时cost中减去,最终答案就是n-ans。
1 #include <cstdio> 2 #include <queue> 3 #include <algorithm> 4 using namespace std; 5 6 const int maxn = 800000 + 5; 7 8 int n; 9 pair<int, int> work[maxn];10 11 int main() {12 int T;13 scanf("%d", &T);14 while (T--) {15 scanf("%d", &n);16 for (int i = 0, a, b; i < n; i++) {17 scanf("%d%d", &a, &b);18 work[i].first = b;19 work[i].second = a;20 }21 sort(work, work + n);22 priority_queue<int> pq;23 int ans = 0, cost = 0;24 for (int i = 0; i < n; i++) {25 cost += work[i].second;26 pq.push(work[i].second);27 if (cost > work[i].first) {28 cost -= pq.top();29 pq.pop();30 ans++;31 }32 }33 printf("%d\n", n - ans);34 if (T) printf("\n");35 }36 return 0;37 }
UVa1153 Keep the Customer Satisfied (贪心,优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。