Lisa Keffer @ unsplash.com
一道 PAT 原题,被称为「PAT史上最麻烦题目」:
一个乒乓球俱乐部共有
张乒乓球台,编号为
。
对于任意一对球员,当他们到达时如果有多个球台可用,那么他们就会被安排到编号较小的那个球台上打球。
如果所有球台都被占用了,他们就只能排队等待了。
假设每对球员最多只允许打两小时球。
你需要计算每个排队等候的人的等待时间以及每个球台当天有多少对球员在上面打球。
另外,让这个事情变得复杂的是,俱乐部为 VIP 球员保留了一些球台。
当一个 VIP 球台空出时,等待队伍中的第一对 VIP 球员将优先使用这个球台。
如果此时等待队伍中没有 VIP,则排在等待队伍的第一对球员可以使用这个球台。
另一方面,当轮到一对 VIP 球员打球时,如果没有 VIP 球台可用,那么他们将被视作普通球员处理。
第一行包含整数
,表示共有
对球员。
接下来
行,每行包含两个时间以及一个 VIP 标识,HH:MM:SS
----到达时间,p
----打球时间(单位:分钟),tag
----如果是
,说明这是一对 VIP,如果是
,说明不是 VIP。
保证到达时间在 08:00:00
至 21:00:00
之间,这是俱乐部的营业时间。
保证每对球员的到达时间都不相同。
再一行包含两个整数
和
,表示球台数量以及 VIP 球台数量。
最后一行包含
个整数,表示 VIP 球台的编号。
首先输出每对球员的到达时间,开始打球时间,等待时间。
每对球员的信息占一行,按开始打球时间从早到晚的顺序依次输出。
等待时间必须四舍五入为整数分钟。
如果一对球员在 21:00:00
之前(不包括 21:00:00
)不能得到一张球台,那么无需输出他们的信息。
再输出一行,
个整数,表示每个球台服务的球员对数。
,
,
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
A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours.
Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day.
One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the privilege to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.
Each input file contains one test case. For each case, the first line contains an integer N (≤10000) - the total number of pairs of players. Then N lines follow, each contains 2 times and a VIP tag: HH:MM:SS
- the arriving time, P - the playing time in minutes of a pair of players, and tag - which is 1 if they hold a VIP card, or 0 if not. It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open. It is assumed that no two customers arrives at the same time. Following the players' info, there are 2 positive integers: K (≤100) - the number of tables, and M (< K) - the number of VIP tables. The last line contains M table numbers.
For each test case, first print the arriving time, serving time and the waiting time for each pair of players in the format shown by the sample. Then print in a line the number of players served by each table. Notice that the output must be listed in chronological order of the serving time. The waiting time must be rounded up to an integer minute(s). If one cannot get a table before the closing time, their information must NOT be printed.
思路:
Player
放入相应的优先队列,被分配了就把 Player
弹出来,被分配到的 Table
也弹出来,更新结束时间,再放入 Table 对应的队列注意事项:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
const int N = 1e4 + 10, M = 1e2 + 10, INF = 2e9;
int n, k, m;
struct Player
{
int arrive_time, serve_time;
int start_time, waiting_time;
// 给 sort 排
const bool operator< (const Player& t) const
{
if (start_time != t.start_time) return start_time < t.start_time;
return arrive_time < t.arrive_time;
}
// 给 priority_queue 排
const bool operator> (const Player& t) const
{
return arrive_time > t.arrive_time;
}
};
struct Table
{
int id;
int end_time;
const bool operator> (const Table& t) const
{
if (end_time != t.end_time) return end_time > t.end_time;
return id > t.id;
}
};
bool is_vip_table[M];
int table_count[M];
// 最终输出的玩家及顺序
vector<Player> players;
// 注意 `&` 很重要
void assign(priority_queue<Player, vector<Player>, greater<Player>>& ps,
priority_queue<Table, vector<Table>, greater<Table>>& ts)
{
auto p = ps.top();
ps.pop();
auto t = ts.top();
ts.pop();
int start_time = t.end_time;
int end_time = start_time + p.serve_time;
ts.push({t.id, end_time});
table_count[t.id] ++;
p.start_time = start_time;
p.waiting_time = round((start_time - p.arrive_time) / 60.0);
players.push_back(p);
}
string time_to_string(int sec)
{
char str[20];
sprintf(str, "%02d:%02d:%02d", sec / 3600, sec % 3600 / 60, sec % 60);
return str;
}
int main()
{
// 输入玩家
priority_queue<Player, vector<Player>, greater<Player>> normal_players;
priority_queue<Player, vector<Player>, greater<Player>> vip_players;
normal_players.push({INF});
vip_players.push({INF});
cin >> n;
for (int i = 0; i < n; i ++ )
{
int hour, minute, sec;
int serve_time, is_vip;
scanf("%d:%d:%d %d %d", &hour, &minute, &sec, &serve_time, &is_vip);
sec = hour * 3600 + minute * 60 + sec;
serve_time = min(serve_time * 60, 7200);
if (is_vip) vip_players.push({sec, serve_time});
else normal_players.push({sec, serve_time});
}
// 输入桌子
priority_queue<Table, vector<Table>, greater<Table>> normal_tables;
priority_queue<Table, vector<Table>, greater<Table>> vip_tables;
normal_tables.push({-1, INF});
vip_tables.push({-1, INF});
cin >> k >> m;
for (int i = 0; i < m; ++ i)
{
int id;
cin >> id;
is_vip_table[id] = true;
}
for (int i = 1; i <= k; i ++ )
{
if (is_vip_table[i]) vip_tables.push({i, 8 * 3600});
else normal_tables.push({i, 8 * 3600});
}
// 开始分配
while (normal_players.size() > 1 || vip_players.size() > 1)
{
auto np = normal_players.top();
auto vp = vip_players.top();
int cur_time = min(np.arrive_time, vp.arrive_time);
while (normal_tables.top().end_time < cur_time)
{
auto t = normal_tables.top();
normal_tables.pop();
t.end_time = cur_time;
normal_tables.push(t);
}
while (vip_tables.top().end_time < cur_time)
{
auto t = vip_tables.top();
vip_tables.pop();
t.end_time = cur_time;
vip_tables.push(t);
}
auto nt = normal_tables.top();
auto vt = vip_tables.top();
int end_time = min(nt.end_time, vt.end_time);
if (end_time >= 21 * 3600) break;
if (vp.arrive_time <= end_time && vt.end_time == end_time) assign(vip_players, vip_tables);
else if (np.arrive_time < vp.arrive_time)
{
if (nt > vt) assign(normal_players, vip_tables);
else assign(normal_players, normal_tables);
}
else
{
if (nt > vt) assign(vip_players, vip_tables);
else assign(vip_players, normal_tables);
}
}
sort(players.begin(), players.end());
for (auto p: players)
{
cout << time_to_string(p.arrive_time) << " " << time_to_string(p.start_time) << " " << p.waiting_time << endl;
}
for (int i = 1; i <= k; i ++ )
{
cout << table_count[i];
if (i + 1 <= k) cout << " ";
else cout << endl;
}
}