首页 > 代码库 > UVA10588 - Queuing at the doctors(优先队列)
UVA10588 - Queuing at the doctors(优先队列)
题目:UVA10588 - Queuing at the doctors(优先队列)
题目大意:员工体检:总共有M个医生,每个医生每一秒接待一位员工,然后每个员工都有一份检查列表,上面的检查顺序要被严格的执行,问这样检查最后一个员工离开诊所的时间。
解题思路:队列模拟,用优先队列来储存每个office的客人列表,记录进来的时间和序号。时间相同的序号小的优先,否则时间早的优先。然后给一个当前的时间now,在这个时间之前的病房前的第一个客人先体检,然后在将这个客人放到他下个要去的office的队列中。一直到病房里没有客人了,输出最后的now。
代码:
#include <cstdio> #include <queue> #include <cstring> using namespace std; const int N = 1005; const int INF = 1e6 + 5; typedef long long ll; struct Person { int th; ll t; Person () {} Person (int th, ll t): th(th), t(t) {} bool operator < (const Person &a) const { return t > a.t || (t == a.t && th > a.th); } }; priority_queue<Person> q[N];//office等待员工的队列 queue<int> p[N];//员工的检查清单 ll t[N]; int main () { int T; int n, m, k, item; int P; ll now; scanf ("%d", &T); while (T--) { scanf ("%d%d", &n, &m); now = INF; for (int i = 0; i < n; i++) { scanf ("%lld%d", &t[i], &k); now = min (now, t[i]); while (k--) { scanf ("%d", &item); p[i].push(item); } } for (int i = 0; i < n; i++) { if (!p[i].empty()) { P = p[i].front(); p[i].pop(); q[P].push(Person(i, t[i])); } } Person person; while (1) { for (int i = 1; i <= m; i++) { if (!q[i].empty()) { person = q[i].top(); if (person.t > now) continue; if (!p[person.th].empty()) { P = p[person.th].front(); p[person.th].pop(); q[P].push(Person(person.th, now + 1)); } q[i].pop(); } } // printf ("%lld\n", now); ll min_n = INF; for (int i = 1; i <= m; i++) { if (!q[i].empty()) min_n = min (min_n, q[i].top().t); } now++; if (min_n != INF) now = max (now, min_n); else break; } printf ("%lld\n", now); } return 0; }
UVA10588 - Queuing at the doctors(优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。