PAT 甲级 1026 Table Tennis

原题链接: https://pintia.cn/problem-sets/994805342720868352/problems/994805472333250560

题目信息：

1026 Table Tennis (30 分)

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.

Sample Input:

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

Sample Output:

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的设定，所以从玩家视角稍微繁琐一些，我们就用时间视角来做。

PAT很多时间类模拟题时间给的都是充裕的，因此我们只要搞清楚题意，理清思路，细心一些就很容易AC。

这类题目一般的处理方式就是把时间转换成秒，按时刻模拟事件。

解题思路：

对于每一个时刻：

首先清空桌子上该时刻需要走的玩家；

然后把该时刻来的玩家放在相应的队列里；

根据空余桌子的情况处理玩家{

我们首先处理vip桌子存在且有vip玩家排队情况，此时刻按照题意"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." "When a VIP table is open, the first VIP pair in the queue will have the privilege to take it."，所以一定先安排vip玩家选择最小vip桌子。

上一步操作完成后，此时一定不会同时存在vip桌子和vip玩家；那么所有的对象一视同仁，都做普通处理就好了。

}

细节点：

"It is assumed that every pair of players can play for at most 2 hours"，很多人把这里 assumed理解成假设的意思，实际上在英文表达中，"It is assumed that ……"，常常表示一种被认为，默认的情形，所以这句理解成：默认每对玩家最多能玩两小时。因此我们要处理这个输入信息。

最后的时刻21:00:00是不能进场的；

时间四舍五入的处理；

致谢：

感谢b站弄夫大佬帮我改程序，解决了队列访问的bug，可以参考一下大佬的视频题解https://b23.tv/iNSZ6y

AC代码：

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = 10001, MAX_K = 101;
queue<int> qv, qo;
int ans[MAX_N], nums = 0;

int getTime(int h, int m, int s) { return h*3600 + m*60 + s;}

const int BEGIN = getTime(8, 0, 0), END = getTime(21, 0, 0), MAX_PLAY = getTime(2, 0, 0);

void prinTime(int t) { printf("%02d:%02d:%02d ", t/3600, t%3600/60, t%60);}

struct Player {
    int arrTime, serTime = -1, playTime, leaveTime;
    bool isVip;
    Player(int a = -1, int p = -1, bool t = false) : arrTime(a), playTime(p), isVip(t) {}
}players[MAX_N];

struct Table {
    int use = -1, count = 0;
    bool isVip = false;
}tables[MAX_K];

bool cmpArrTime(Player a, Player b) { return a.arrTime < b.arrTime;}

void goPlay(int p, int i, int t) {//更新入场后的信息: 玩家p 在i号桌 t时刻入场打球
    ans[nums++] = p;   //ans数组按时间顺序记录每个进场打球的玩家
    tables[i].use = p;
    tables[i].count ++;
    players[p].serTime = t;
    players[p].leaveTime = t + players[p].playTime;
}

int main() {
    int N, K, M;
    int h, m, s, pt, tag, p, cur = 0;

    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        scanf("%d:%d:%d%d%d", &h, &m, &s, &pt, &tag);
        players[i] = Player(getTime(h,m,s), min(MAX_PLAY, getTime(0,pt,0)), tag==1);
    }

    scanf("%d%d", &K, &M);
    for(int i = 0; i < M; ++i) {
        scanf("%d", &tag);
        tables[tag-1].isVip = true;
    }//至此完成所有信息读入

    sort(players, players+N, cmpArrTime);
    for(int t = BEGIN; t < END; ++t) {//时间驱动模拟
        for(int i = 0; i < K; ++i) {//重置球桌，把球桌中此刻要走的玩家清除
            p = tables[i].use;
            if(p >= 0 && players[p].leaveTime == t) tables[i].use = -1;   
        }

        if(cur < N && players[cur].arrTime == t) {//把此刻来的人放进队列
            if(players[cur].isVip) qv.push(cur);
            else qo.push(cur);
            cur++;
        }

        for(int i = 0; i < K; ++i) {// 如果有vip排队，匹配空闲vip桌
            if(qv.empty()) break;
            if(tables[i].isVip && tables[i].use == -1 ) {
                p = qv.front();
                goPlay(p, i, t);
                qv.pop();
            }  
        }
        
        for(int i = 0; i < K; ++i) {// 只要有人排队，我们就把所有对象当普通的处理
            if(qv.empty() && qo.empty()) break;
            if(tables[i].use ==-1) {
                if(qv.empty() || qo.size() && qo.front() < qv.front()) p = qo.front();
                else p = qv.front();////返回队列中最早入队的人p
                goPlay(p, i, t);
                if(qv.size() && p == qv.front()) qv.pop();
                else qo.pop();
            }
        }
    }

    for(int i = 0; i < nums; ++i) {
        p = ans[i];
        prinTime(players[p].arrTime);
        prinTime(players[p].serTime);
        printf("%d\n", (players[p].serTime - players[p].arrTime + 30) / 60);
    }

    for(int i = 0; i < K; ++i) {
        printf("%d",tables[i].count);
        if(i < K-1) printf(" ");
    }
    return 0;
}