題目如下：

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 priviledge 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

題目要求對(duì)乒乓球廳的事件進(jìn)行模擬。

根據(jù)用戶到達(dá)時(shí)間排隊(duì)，有空桌子則按先到先服務(wù)的原則處理，如果隊(duì)列中有VIP用戶并且有VIP桌子空閑，則VIP可以“自成一隊(duì)”，按照到達(dá)順序直接分配到VIP桌，如果沒(méi)有VIP桌空閑，則VIP和普通用戶同樣對(duì)待。如果隊(duì)中沒(méi)有VIP并且編號(hào)最小的恰是VIP桌，普通用戶也可以使用VIP桌。

這類(lèi)題目需要處理桌子的空閑與用戶的到達(dá)、服務(wù)時(shí)間之間的關(guān)系，需要有一個(gè)較好的思路，否則很容易混亂。

一個(gè)比較好的思路是為每個(gè)桌子設(shè)定空閑時(shí)間，首先全部初始化為上午8:00，當(dāng)處理一個(gè)人時(shí)，首先從桌子列表最前面取到桌子，然后根據(jù)自己的到達(dá)時(shí)間和桌子的空閑時(shí)間即可計(jì)算出桌子的新空閑時(shí)間、用戶的等待時(shí)間和服務(wù)時(shí)間（有可能到關(guān)門(mén)時(shí)達(dá)不到預(yù)期服務(wù)時(shí)間）。

這道題麻煩在VIP上，如果有VIP用戶，他們可以“插隊(duì)”，要處理這些用戶，就會(huì)讓問(wèn)題變得復(fù)雜，不能簡(jiǎn)單的取出第一個(gè)未服務(wù)用戶和第一個(gè)桌子，而是要考慮有VIP用戶和VIP桌子的情況，這里有兩種優(yōu)秀的解法：

①類(lèi)似歸并排序的思想，維護(hù)普通用戶和VIP用戶兩個(gè)隊(duì)列。

②僅使用一個(gè)隊(duì)列，先考慮VIP情況，沒(méi)有VIP被處理則按照正常情況處理，算法來(lái)自sunbaigui。

我完整的參考了sunbaigui的解法，他的解法非常巧妙，下面羅列一下關(guān)鍵點(diǎn)：

①對(duì)用戶排序后從前到后處理，初始化服務(wù)開(kāi)始時(shí)間為INF，這樣當(dāng)處理完一個(gè)人時(shí)，他的服務(wù)時(shí)間不再是INF，由此判斷是否處理完畢，不必另設(shè)標(biāo)志。

②不對(duì)桌子排序，而是找到所有桌子中空閑時(shí)間最早的，從桌子列表從前到后篩選，這樣就保證了按照編號(hào)的順序，十分巧妙。

③根據(jù)②中找到的最早空閑時(shí)間，找出所有符合的桌子和用戶，分別存儲(chǔ)一個(gè)新的容器，后面就針對(duì)這兩個(gè)新的容器處理。

④分情況討論，單人單桌、多人單桌、多人多桌，在這三種情況下分別判斷是否有VIP被服務(wù)。

⑤如果④中沒(méi)有VIP被服務(wù)，則取出新容器中第一個(gè)用戶和第一個(gè)桌子，正常處理。

下面的代碼來(lái)自sunbaigui，我在他代碼的基礎(chǔ)上加了些注釋，方便理解。

#include<iostream> #include<vector> #include<set> #include<map> #include<queue> #include<algorithm> #include<string> #include<string.h> #include<stdio.h>using namespace std;typedef struct Node {int arrive, process, tag;int serve, wait; // serve和wait分別代表服務(wù)開(kāi)始時(shí)間和等待時(shí)間，將serve初始化為INF，從而區(qū)分有沒(méi)有被服務(wù) }Node; typedef struct Table {int tag;int freeTime, num; // 每個(gè)桌子記錄自己的空閑時(shí)間和服務(wù)數(shù)，全部初始化為上午8:00，這樣可以迭代著處理 }Table; bool CmpArrive(Node a, Node b) // 用于對(duì)用戶的到達(dá)時(shí)間升序排序 {return a.arrive < b.arrive; } bool CmpServe(Node a, Node b) // 對(duì)用戶按照時(shí)間順序排列，優(yōu)先按照服務(wù)時(shí)間排序，如果服務(wù)同時(shí)開(kāi)始（多個(gè)空桌），按照到達(dá)時(shí)間升序 {if(a.serve == b.serve)return a.arrive < b.arrive;else return a.serve < b.serve; } #define INF 0x6FFFFFFFvector<Node> user; vector<Table> table; void UpdateInfo(int userID, int tableID) {user[userID].serve = max(user[userID].arrive, table[tableID].freeTime);user[userID].wait = user[userID].serve-user[userID].arrive;table[tableID].num++;table[tableID].freeTime = user[userID].serve+min(user[userID].process, 7200); // 最長(zhǎng)服務(wù)時(shí)間為2小時(shí) } int main() {//inputint n;scanf("%d",&n);user.resize(n);for(int i = 0; i < n; ++i){int h, m, s;scanf("%d:%d:%d %d%d",&h,&m,&s,&user[i].process,&user[i].tag);user[i].arrive = h*3600+m*60+s;user[i].process *= 60;user[i].serve = INF; user[i].wait = INF; // 初始化為INF，INF就代表未被處理}int k, m;scanf("%d%d",&k,&m);table.resize(k);for(int i = 0; i < k; ++i)table[i].freeTime = 8*3600, table[i].tag = 0, table[i].num = 0; // 所有桌子從上午8:00開(kāi)始可用for(int i = 0; i < m; ++i){int c;scanf("%d",&c); c--;table[c].tag = 1;}//processsort(user.begin(), user.end(), CmpArrive); // 按照到達(dá)時(shí)間升序排列，符合排隊(duì)規(guī)則//visited.assign(n, false);for(int i = 0; i < n; ++i){if(user[i].serve != INF) continue; // server時(shí)間初始化為INF，不為INF的已經(jīng)服務(wù)完畢。int minFreeTime = INF;for(int j = 0; j < k; ++j)minFreeTime = min(minFreeTime, table[j].freeTime); // 找出最早空閑的桌子int timePoint = max(user[i].arrive, minFreeTime); // 根據(jù)隊(duì)頭用戶確定當(dāng)前最早服務(wù)時(shí)間點(diǎn)if(timePoint >= 21*3600) break; // 判斷是否超過(guò)營(yíng)業(yè)時(shí)間vector<int> userList;vector<int> tableList;for(int j = i; j < n; ++j) // 根據(jù)最早服務(wù)時(shí)間點(diǎn)找到所有可能被服務(wù)的人，是為了處理有VIP優(yōu)先去VIP桌的情況。if(user[j].serve == INF && user[j].arrive <= timePoint) userList.push_back(j);for(int j = 0; j < k; ++j) // 找出所有在時(shí)間點(diǎn)之前空閑的桌子，因?yàn)榭赡苡脩舻竭_(dá)晚，因此會(huì)有多個(gè)桌子空閑if(table[j].freeTime <= timePoint) tableList.push_back(j);bool flag = false; // 判斷是否處理了一個(gè)服務(wù)// 首先特殊處理VIP，如果沒(méi)有VIP被處理則處理一個(gè)普通用戶，每次只處理一個(gè)if(userList.size() == 1 && tableList.size() > 1) // 單個(gè)用戶多個(gè)桌子，用戶為VIP則去找編號(hào)最小的VIP桌{if(user[userList[0]].tag == 1){for(int j = 0; j < tableList.size(); ++j){if(table[tableList[j]].tag == 1){flag = true;UpdateInfo(userList[0], tableList[j]);break;}}}}else if(tableList.size() == 1 && userList.size() > 1) // 多人單桌情況，如果為VIP桌找多人中最先到達(dá)的VIP為其服務(wù){(diào)if(table[tableList[0]].tag == 1){for(int j = 0; j < userList.size(); ++j){if(user[userList[j]].tag == 1){flag = true;UpdateInfo(userList[j], tableList[0]);break;}}}}else if(tableList.size() > 1 && userList.size() > 1) // 多人多桌情況，先找桌子中的VIP桌，有則找用戶中最先到達(dá)的VIP{for(int t = 0; t < tableList.size(); ++t){if(table[tableList[t]].tag == 1){for(int u = 0; u < userList.size(); ++u){if(user[userList[u]].tag == 1){flag = true;UpdateInfo(userList[u], tableList[t]);break;}}}}}if(!flag) UpdateInfo(userList[0], tableList[0]); // 如果沒(méi)有VIP被處理，則按照正常情況處理。--i;}//outputsort(user.begin(), user.end(), CmpServe);for(int i = 0; i < n; ++i){if(user[i].serve >= 21*3600) break;int h1, m1, s1, h2, m2, s2;int t = user[i].arrive;h1 = t/3600; t %= 3600;m1 = t/60; t %= 60;s1 = t;t = user[i].serve;h2 = t/3600; t %= 3600;m2 = t/60; t %= 60;s2 = t;// 注意對(duì)等待時(shí)間的四舍五入為超過(guò)30秒算作一分鐘printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", h1, m1, s1, h2, m2, s2, (user[i].wait+30)/60);}for(int i = 0; i < k; ++i){if(i != k-1)printf("%d ",table[i].num);else printf("%d\n",table[i].num);}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/aiwz/p/6154036.html

總結(jié)

以上是生活随笔為你收集整理的1026. Table Tennis (30)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。