题目
一个乒乓球俱乐部共有 K 张乒乓球台，编号为 1∼K。
对于任意一对球员，当他们到达时如果有多个球台可用，那么他们就会被安排到编号较小的那个球台上打球。
如果所有球台都被占用了，他们就只能排队等待了。
假设每对球员最多只允许打两小时球。
你需要计算每个排队等候的人的等待时间以及每个球台当天有多少对球员在上面打球。
另外，让这个事情变得复杂的是，俱乐部为 VIP 球员保留了一些球台。
当一个 VIP 球台空出时，等待队伍中的第一对 VIP 球员将优先使用这个球台。
如果此时等待队伍中没有 VIP，则排在等待队伍的第一对球员可以使用这个球台。
另一方面，当轮到一对 VIP 球员打球时，如果没有 VIP 球台可用，那么他们将被视作普通球员处理。
补充：
1、当等待队伍中有 VIP 球员并且有空闲 VIP 球台时，必须优先分配 VIP 球员，并且必须分配他们 VIP 球台（优先分配编号较小的），直至 VIP 用户或 VIP 球台分配完为止。
2、期望打球时间超过两小时的，只能允许打两小时。
3、当多对球员的开始打球时间相同时，先输出到达时间早的球员的信息。
4、当等待球员中没有 VIP 时，VIP 球台视作普通球台处理，当可用球台中没有 VIP 球台时，VIP 球员视作普通球员处理。
输入格式
第一行包含整数 N，表示共有 N 对球员。
接下来 N 行，每行包含两个时间以及一个 VIP 标识，HH:MM:SS——到达时间，p——打球时间（单位：分钟），tag——如果是 1，说明这是一对 VIP，如果是 0，说明不是 VIP。
保证到达时间在 08:00:00 至 21:00:00 之间，这是俱乐部的营业时间。
保证每对球员的到达时间都不相同。
再一行包含两个整数 K 和 M，表示球台数量以及 VIP 球台数量。
最后一行包含 M 个整数，表示 VIP 球台的编号。
输出格式
首先输出每对球员的到达时间，开始打球时间，等待时间。
每对球员的信息占一行，按开始打球时间从早到晚的顺序依次输出。
等待时间必须四舍五入为整数分钟。
如果一对球员在 21:00:00 之前(不包括 21:00:00）不能得到一张球台，那么无需输出他们的信息。
再输出一行，K 个整数，表示每个球台服务的球员对数。
数据范围
1≤N≤10000,
1≤K≤100,
0≤M≤K
输入样例：
9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 5 0
08:12:00 10 1
20:50:00 10 0
08:01:30 15 1
20:53:00 10 1
3 1
2
输出样例：
08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:12:00 08:16:30 5
08:10:00 08:20:00 10
20:50:00 20:50:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
3 3 2

解法：模拟

vip机制：
1. 若等待队列中有vip,且有vip桌空闲，则优先服务vip
2. 有vip无vip球桌，则vip视为普通人
有vip桌无vip,则vip桌视为普通球桌
已有空余球桌
a. 该同学是vip，则分配vip球桌
b. 该同学不是vip，则分配编号最小的球桌
没有空余球桌，求最早结束时间
a. 最早结束的是普通球桌，一视同仁
b. 最早结束的是vip球桌，vip同学先上

技巧：

  • 设置哨兵，不用考虑判空
  • 将有空余球桌转化为没有空余球桌

时间复杂度O(nklogk)，空间复杂度O(n+k)

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <queue>
  5. #include <cmath>
  7. using namespace std;
  9. const int N = 1e4 + 5, M = 105, INF = 1e9;
  11. struct User {
  12.     int arr, dur;
  13.     int start, wait;
  15.     bool operator > (const User &u) const {
  16.         return arr > u.arr;
  17.     }
  18. };
  19. vector<User> show;
  20. priority_queue<User, vector<User>, greater<User>> users;
  21. priority_queue<User, vector<User>, greater<User>> vipUsers;
  23. // bool cmp_arr(const User &a, const User &b) {
  24. //     return a.arr < b.arr;
  25. // }
  27. bool cmp_start(const User &a, const User &b) {
  28.     if (a.start != b.start) return a.start < b.start;
  29.     return a.arr < b.arr;
  30. }
  32. struct Table {
  33.     int w, id;
  35.     bool operator > (const Table &t) const {
  36.         if (w != t.w) return w > t.w;
  37.         return id > t.id;
  38.     }
  39. };
  40. priority_queue<Table, vector<Table>, greater<Table>> tables;
  41. priority_queue<Table, vector<Table>, greater<Table>> vipTables;
  42. int table_cnt[M];
  43. bool table_vip[M];
  45. string get_time(int s) {
  46.     char t[10];
  47.     sprintf(t, "%02d:%02d:%02d", s / 3600, s % 3600 / 60, s % 60);
  48.     return t;
  49. }
  51. int main() {
  52.     int n;
  53.     cin >> n;
  55.     for (int i = 0; i < n; i++) {
  56.         int h, m, s, dur, vip;
  57.         scanf("%d:%d:%d %d %d", &h, &m, &s, &dur, &vip);
  58.         int t = h * 3600 + m * 60 + s;
  59.         dur = min(dur, 120) * 60;
  60.         if (vip)
  61.             vipUsers.push({t, dur});
  62.         else users.push({t, dur});
  63.     }
  64.     users.push({INF}), vipUsers.push({INF});
  66.     int k, m;
  67.     cin >> k >> m;
  68.     for (int i = 0; i < m; i++) {
  69.         int id;
  70.         scanf("%d", &id);
  71.         table_vip[id] = true;
  72.     }
  73.     for (int i = 1; i <= k; i++) {
  74.         if (table_vip[i]) vipTables.push({8 * 3600, i});
  75.         else tables.push({8 * 3600, i});
  76.     }
  77.     tables.push({INF, -1}), vipTables.push({INF, -1});
  79.     while (users.size() > 1 || vipUsers.size() > 1) {
  80.         auto u = users.top(), vipu = vipUsers.top();
  81.         int arr = min(u.arr, vipu.arr);
  83.         while (tables.top().w < arr) {
  84.             auto t = tables.top();
  85.             tables.pop();
  86.             t.w = arr;
  87.             tables.push(t);
  88.         }
  89.         while (vipTables.top().w < arr) {
  90.             auto t = vipTables.top();
  91.             vipTables.pop();
  92.             t.w = arr;
  93.             vipTables.push(t);
  94.         }
  96.         auto t = tables.top(), vipt = vipTables.top();
  97.         int w = min(t.w, vipt.w);
  98.         if (w >= 21 * 3600) break;
  100.         if (vipu.arr <= w && w == vipt.w) {
  101.             vipu.start = max(vipu.arr, vipt.w);
  102.             vipu.wait = vipu.start - vipu.arr;
  103.             vipUsers.pop();
  104.             show.push_back(vipu);
  106.             table_cnt[vipt.id]++;
  107.             vipTables.pop();
  108.             vipTables.push({vipu.start + vipu.dur, vipt.id});
  109.         }
  110.         else if (u > vipu) {
  111.             if (t > vipt) {
  112.                 vipu.start = max(vipu.arr, vipt.w);
  113.                 vipu.wait = vipu.start - vipu.arr;
  114.                 vipUsers.pop();
  115.                 show.push_back(vipu);
  117.                 table_cnt[vipt.id]++;
  118.                 vipTables.pop();
  119.                 vipTables.push({vipu.start + vipu.dur, vipt.id});
  120.             }
  121.             else {
  122.                 vipu.start = max(vipu.arr, t.w);
  123.                 vipu.wait = vipu.start - vipu.arr;
  124.                 vipUsers.pop();
  125.                 show.push_back(vipu);
  127.                 table_cnt[t.id]++;
  128.                 tables.pop();
  129.                 tables.push({vipu.start + vipu.dur, t.id});
  130.             }
  131.         }
  132.         else {
  133.             if (t > vipt) {
  134.                 u.start = max(u.arr, vipt.w);
  135.                 u.wait = u.start - u.arr;
  136.                 users.pop();
  137.                 show.push_back(u);
  139.                 table_cnt[vipt.id]++;
  140.                 vipTables.pop();
  141.                 vipTables.push({u.start + u.dur, vipt.id});
  142.             }
  143.             else {
  144.                 u.start = max(u.arr, t.w);
  145.                 u.wait = u.start - u.arr;
  146.                 users.pop();
  147.                 show.push_back(u);
  149.                 table_cnt[t.id]++;
  150.                 tables.pop();
  151.                 tables.push({u.start + u.dur, t.id});
  152.             }
  153.         }
  154.     }
  156.     sort(show.begin(), show.end(), cmp_start);
  158.     for (auto &u: show) {
  159.         printf("%s %s %.0lf\n", get_time(u.arr).c_str(), get_time(u.start).c_str(), round(u.wait / 60.0));
  160.     }
  162.     printf("%d", table_cnt[1]);
  163.     for (int i = 2; i <= k; i++)
  164.         printf(" %d", table_cnt[i]);
  166.     return 0;
  167. }