首页 > 代码库 > UVA1153-Keep the Customer Satisfied(贪心+优先队列)
UVA1153-Keep the Customer Satisfied(贪心+优先队列)
题目链接
题意:有一家大型的钢铁厂,每月初都收到大量客户的订单,订单包括定制的钢铁的数量q,以及交货的截止时间d。每个单位时间只能完成一个订单的工作,不能同时进行多个,要求怎么安排使得接受的订单最多。
思路:要使得订单最多,首先我们先按照截止日期,从小到大排序。
当
#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm> using namespace std; const int MAXN = 800005; const int N = 2000005; struct order{ int q, d; }o[MAXN]; int n; int cmp (order a, order b) { return a.d < b.d; } int solve() { priority_queue<int> Q; int t = 0, temp; for (int i = 0; i < n; i++) { if (o[i].q + t <= o[i].d) { Q.push(o[i].q); t += o[i].q; } else if (!Q.empty()){ temp = Q.top(); if (temp > o[i].q) { t = t - temp + o[i].q; Q.pop(); Q.push(o[i].q); } } } return Q.size(); } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d", &n); for (int i = 0; i < n; i++) scanf("%d%d", &o[i].q, &o[i].d); sort(o, o + n, cmp); printf("%d\n", solve()); if (cas) printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。