[[418167]]

本文轉(zhuǎn)載自微信公眾號「Piper蛋窩」，作者Piper蛋。轉(zhuǎn)載本文請聯(lián)系Piper蛋窩公眾號。

一道 PAT 原題，被稱為「PAT史上最麻煩題目」：

• PAT 原題英文鏈接：https://pintia.cn/problem-sets/994805342720868352/problems/994805472333250560
• AcWing 翻譯：https://www.acwing.com/problem/content/1505/

原題

一個乒乓球俱樂部共有K張乒乓球臺，編號為1~K 。

對于任意一對球員，當他們到達時如果有多個球臺可用，那么他們就會被安排到編號較小的那個球臺上打球。

如果所有球臺都被占用了，他們就只能排隊等待了。

假設每對球員最多只允許打兩小時球。

你需要計算每個排隊等候的人的等待時間以及每個球臺當天有多少對球員在上面打球。

另外，讓這個事情變得復雜的是，俱樂部為 VIP 球員保留了一些球臺。

當一個 VIP 球臺空出時，等待隊伍中的第一對 VIP 球員將優(yōu)先使用這個球臺。

如果此時等待隊伍中沒有 VIP，則排在等待隊伍的第一對球員可以使用這個球臺。

另一方面，當輪到一對 VIP 球員打球時，如果沒有 VIP 球臺可用，那么他們將被視作普通球員處理。

補充：

1、當?shù)却犖橹杏?VIP 球員并且有空閑 VIP 球臺時，必須優(yōu)先分配 VIP 球員，并且必須分配他們 VIP 球臺(優(yōu)先分配編號較小的)，直至 VIP 用戶或 VIP 球臺分配完為止。

2、期望打球時間超過兩小時的，只能允許打兩小時。

3、當多對球員的開始打球時間相同時，先輸出到達時間早的球員的信息。

4、當?shù)却騿T中沒有 VIP 時，VIP 球臺視作普通球臺處理，當可用球臺中沒有 VIP 球臺時，VIP 球員視作普通球員處理。

輸入格式

第一行包含整數(shù)N，表示共有N對球員。

接下來N行，每行包含兩個時間以及一個 VIP 標識，HH:MM:SS----到達時間，p----打球時間(單位：分鐘)，tag----如果是 ，說明這是一對 VIP，如果是 ，說明不是 VIP。

保證到達時間在 08:00:00 至 21:00:00 之間，這是俱樂部的營業(yè)時間。

保證每對球員的到達時間都不相同。

再一行包含兩個整數(shù)K和M，表示球臺數(shù)量以及 VIP 球臺數(shù)量。

最后一行包含M個整數(shù)，表示 VIP 球臺的編號。

輸出格式

首先輸出每對球員的到達時間，開始打球時間，等待時間。

每對球員的信息占一行，按開始打球時間從早到晚的順序依次輸出。

等待時間必須四舍五入為整數(shù)分鐘。

如果一對球員在 21:00:00 之前(不包括 21:00:00)不能得到一張球臺，那么無需輸出他們的信息。

再輸出一行，K個整數(shù)，表示每個球臺服務的球員對數(shù)。

數(shù)據(jù)范圍

輸入樣例：

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

1026 Table Tennis (30 point(s))

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.

Input Specification:

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.

Output Specification:

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 和 Table 分別放到四個優(yōu)先隊列里面
  • VIP Player
  • VIP Table
  • normal Player
  • normal Table
• 把所有 Player 放入相應的優(yōu)先隊列，被分配了就把 Player 彈出來，被分配到的 Table 也彈出來，更新結(jié)束時間，再放入 Table 對應的隊列
• 關鍵時間點全靠堆頂輸出
• 因此退出循環(huán)的依據(jù)有兩個：Player 空了，或者沒有 Table 在 21:00 前結(jié)束
• 桌子分配原則：
  • 如果輪到 VIP Player 并且 VIP Table 有空缺，則分配;
  • 如果輪到 normal Player 并且只有 VIP Table 有空缺，分配;
  • 如果輪到 VIP Player 并且只有 VIP Table 有空缺，分配;
  • 其他情況分配 normal Player

注意事項：

• 往各個優(yōu)先隊列輸入 INF 的時間原始，且保證其永遠不會到達堆頂，這樣不用判斷是不是空節(jié)點
• 每次四個優(yōu)先隊列都出隊堆頂，方便書寫
• 對于每個玩家關鍵時間點 cur_time ，如果有桌子的 end_time 比這個小，則更新 end_time 為這個 cur_time ，防止后面漏判空余桌子

#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; 
    } 
}