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 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
題目解讀
某乒乓球場每天服務時間是8:00 -- 21:00，有·K個桌子（編號 1-K），其中M個為會員預留，某一天，有N個玩家要來打球，給出了他們的到達時間，玩耍時間，和他們是否是會員，要求，輸出這些玩家的 到達時間 開始被服務時間 玩耍時間。輸出每個桌子服務的人數。
需要注意的是：
21:00及之後到來的玩家無法被服務，這些玩家不用考慮；- 由於排隊等待導致
21:00前還未能被服務的玩家也要在輸出中排除； - 每個乒乓球求桌子限制最多一次服務
2個小時； - 所有的輸出順序要
按照玩家開始被服務時間的先後順序。 - vip玩家的服務優先順序高於普通玩家。當沒有會員來時，vip桌子也為普通用戶服務。這個的具體理解我在思路中細說。
思路解析
說實話這個題目難度不高，無非就是先來先服務，也就是所有玩家按照到達的先後順序排序然後逐個處理，只不過vip可以” 插隊 “ 就導致分類討論比較複雜一點。
框架步驟
- 創建結構體
Player保存玩家的 到達時間、開始被服務時間、玩耍時間、是否是會員。
struct Player {
// 到達時間，開始時間，玩耍時間
int arrive_time, start_time, play_time;
bool isvip; // 是否是 vip
};
- 創建結構體
Table保存每個桌子 何時結束當前服務、服務了幾個人、是不是為vip預留。所有桌子剛開始都是8:00開始服務，所以end_time欄位初始化為8 * 3600。
struct Table {
// 當前服務結束時間，已服務玩家個數
// 剛開始全是8:00開始服務
int end_time = club_open_time, serve_count;
bool isvip; // 是否是為vip預留的桌子
};
- 用
vector保存玩家資訊和桌子資訊。 - 把所有時間都轉換為以
00:00:00開始的秒數進行處理。 - 逐個讀入玩家的資訊，對於到達時間在
21:00及之後的不予理睬。對於」合法「用戶，如果玩耍時間超過兩小時，將其值賦為7200s，將被開始服務時間初始化為21:00，這樣做的目的是，所有得到服務的玩家這個欄位一定會被改變成小於21:00的時間，最終在輸出時能很方便的過濾掉那些未被服務的玩家資訊。 - 對所有玩家按照
到達時間進行排序。 - 逐個處理」玩家「，分類四種討論，我們下面單獨拿出來說它。
- 處理完所有玩家，按照被服務的開始時間排序
- 輸出結果（過率掉未被服務玩家）
第7步細說（對每個玩家的處理）
-
找到所有桌子中最早結束當前服務的桌子，序號為
index。 -
如果這個桌子當前服務的結束時間
>= 21 * 3600，那剩下的玩家都不用處理了，不可能被服務。否則再繼續下面的過程。 -
如果這個桌子是為vip預留的：
3.1 如果這個人是vip，這個桌子分配給他。i++處理下一個人
3.2 這個人不是vip，除非他後面沒有vip到來，桌子才給他用：找到他後面第一個vip；
- 如果vip不存在，那麼這個桌子給直接給他用。
- 如果vip存在，那麼這個桌子給vip用，對嗎？？？注意這是錯誤的！！！除非這個vip在這個桌子當前服務結束之前來了，這個vip才能插隊啊。他都沒來插什麼隊。
- 你不是說vip存在了嗎？存在了為什麼又說他沒來。你要區分現實生活和程式的區別，現實生活中你一眼看到你後面沒有人你說不存在，但程式一次性把所有人資訊都保存在數組裡了，你肉眼去看數組元素肯定存在啊，但是你要去看他的到達時間是不是在這個窗口結束當前服務之間，如果不是，那就是說這個窗口結束服務了，但是，我後面那個所謂」存在「的vip沒有到達，不就相當於沒有嗎？好好想一下，我就是漏了這個一個條件，只得了15分，就在if裡面加上一個 && xxxx，立馬滿分！
-
如果這個桌子是普通桌子：
4.1 如果這個人是普通人，那麼這個桌子分配給他。i++處理下一個人
4.2 如果這個人是vip，首先去看在他來之前有沒有空下來的vip桌子，如果有，就讓他去那個vip桌子，如果沒有，就把這個普通桌子給他用。i++處理下一個人。
現在我們要處理兩個問題
-
分配桌子是幹嘛？
把某個桌子分配給某個玩家就是：更新這個玩家開始被服務的時間；更新這個桌子開始為這個玩家服務後，結束服務的時間
void AssignTableForPlayer(int t_id, int p_id) {
// 玩家來的時候，這個桌子已空閑，玩家可以直接開始玩
if (table[t_id].end_time <= player[p_id].arrive_time) {
player[p_id].start_time = player[p_id].arrive_time;
} else {
// 玩家來的時候這個桌子還在服務上一個人，需要等它當前服務結束
// 所以玩家開始玩的時間應該是這個桌子當前服務結束的時間
player[p_id].start_time = table[t_id].end_time;
}
// 開始新的服務，更新這個桌子當前服務的結束時間
table[t_id].end_time = player[p_id].start_time + player[p_id].play_time;
// 這個桌子的服務人數增加
table[t_id].serve_count++;
}
-
找到這個玩家後面第一個vip的詳細過程是什麼？
多說無益，直接看程式碼
int FindNextVipPlayer(int p_id) {
p_id++;
while (p_id < player.size()) {
if (player[p_id].isvip)
return p_id;
p_id++;
}
// 不存在就返回-1
return -1;
}
-
不是說兩個問題嗎？哪來的3呢？是兩個問題，但是第2個問題有一個大坑啊
假如說這個隊伍是這樣的：1 2 3 4 v1 5 v2
那我問你，處理 1號時找到他後面第一個vip是v1，v1優先被服務了，處理2號時，他後面第一個vip還是v1，難道再給v1服務一次？？不可能嘛，
現實生活中，一個人被服務後就離開了，但我們這是個數組啊，除非你把那個位置數據刪了，否則他就在那，但是你如果刪了那不是要數組元素順序後移或者前移？這浪費的時間可就多了，而且很可能因為粗心大意導致數組越界訪問。
所以我另外創建了一個
bool served[10000]，初始化為false，當某個vip被服務後就把對應位置置為true，避免被重複選取。所以我FindNextVipPlayer也就變成了這樣：
int FindNextVipPlayer(int p_id) {
p_id++;
while (p_id < player.size()) {
// 是會員！且未被服務！
if (player[p_id].isvip && !served[p_id])
return p_id;
p_id++;
}
return -1;
}
同時，在上面 四種分類討論 中，對於碰到的vip玩家，也要加上是不是已經服務過的判斷，如果是就直接跳過它服務下一個人。這一點我在程式碼注釋里寫的很詳細，大家自己看吧。
滿分程式碼
這注釋你要是還看不明白，儘管來打死我！！！！
#include <algorithm>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
// 俱樂部開門時間，以 s 為單位
int club_open_time = 3600 * 8;
// 俱樂部關門時間，以 s 為單位
int club_close_time = 3600 * 21;
// 玩家
struct Player {
// 到達時間，開始時間，玩耍時間
int arrive_time, start_time, play_time;
bool isvip; // 是否是 vip
};
// 桌子
struct Table {
// 當前服務結束時間，已服務玩家個數
// 剛開始全是8:00開始服務
int end_time = club_open_time, serve_count;
bool isvip; // 是否是為vip預留的桌子
};
// 保存玩家，和 桌子
vector<Player> player;
vector<Table> table;
// 比較某個vip是否已經被服務過了
bool served[10000];
// 按到達的先後順序排隊
bool cmp1(Player a, Player b) { return a.arrive_time < b.arrive_time; }
// 輸出時，按被服務時間排序
bool cmp2(Player a, Player b) { return a.start_time < b.start_time; }
// 將某個桌子提供給某個玩家
void AssignTableForPlayer(int t_id, int p_id) {
// 玩家來的時候，這個桌子已空閑，玩家可以直接開始玩
if (table[t_id].end_time <= player[p_id].arrive_time) {
player[p_id].start_time = player[p_id].arrive_time;
} else {
// 玩家來的時候這個桌子還在服務上一個人，需要等它當前服務結束
// 所以玩家開始玩的時間應該是這個桌子當前服務結束的時間
player[p_id].start_time = table[t_id].end_time;
}
// 開始新的服務，更新這個桌子當前服務的結束時間
table[t_id].end_time = player[p_id].start_time + player[p_id].play_time;
// 這個桌子的服務人數增加
table[t_id].serve_count++;
}
// 找到這個人後面第一個會員未被服務的會員，被服務過了就跳過，如果不存在就返回-1
int FindNextVipPlayer(int p_id) {
p_id++;
while (p_id < player.size()) {
// 是會員！且未被服務！
if (player[p_id].isvip && !served[p_id])
return p_id;
p_id++;
}
return -1;
}
int main() {
// n個玩家，k個桌子，m個vip桌子
int n, k, m;
cin >> n;
Player p;
int hh, mm, ss, t, flag;
while (n-- > 0) {
scanf("%d:%d:%d %d %d", &hh, &mm, &ss, &t, &flag);
int arrive = hh * 3600 + mm * 60 + ss;
// 玩家來的時候俱樂部關門，不用管他了
if (arrive >= club_close_time)
continue;
p.arrive_time = arrive;
// 一個玩家最多玩2小時
t = t * 60;
if (t > 7200)
t = 7200;
p.play_time = t;
// 是否是vip
p.isvip = flag == 1 ? true : false;
// 把玩家被服務時間初始化為俱樂部關門時間，便於最後輸出時淘汰掉哪些未被服務的玩家
p.start_time = club_close_time;
// 保存當前玩家
player.push_back(p);
}
cin >> k >> m;
// 桌子從1到K編號
table.resize(k + 1);
// 讀入m個vip桌子序號
int t_id;
while (m-- > 0) {
cin >> t_id;
table[t_id].isvip = true;
}
// 玩家按到達時間排隊
sort(player.begin(), player.end(), cmp1);
int i = 0;
// 逐個處理玩家
while (i < player.size()) {
// 找到第一個結束服務的桌子
int index = -1, min_end = INT_MAX;
for (int j = 1; j <= k; ++j) {
if (table[j].end_time < min_end) {
index = j;
min_end = table[j].end_time;
}
}
// 最早結束的桌子結束當前服務都要等到俱樂部關門了，顧客可以全回家了，沒戲了
if (table[index].end_time >= club_close_time)
break;
// 這個桌子是給會員留的
if (table[index].isvip) {
// 這個人也是會員
if (player[i].isvip) {
// 並且沒被服務過，就直接分配給他，
if (!served[i]) {
AssignTableForPlayer(index, i);
// 標記這個會員被服務
served[i] = true;
// 然後處理下一個人，所以 i++
i++;
} else {
// 服務過了就直接下一個
i++;
}
// 他是普通人
} else {
// 找到他後面第一個vip
// 如果不存在，或者 存在，但是當前桌子結束服務的時候這個vip還沒來，
// 他才可以用這個桌子，
int vip = FindNextVipPlayer(i);
if (vip == -1 || player[vip].arrive_time > table[index].end_time) {
AssignTableForPlayer(index, i);
// 然後處理下一個人，所以 i++
i++;
} else {
// 他後面有會員，而且這個會員的到達時間在這個桌子結束服務之前，
// 這個桌子就給會員用
AssignTableForPlayer(index, vip);
// 標記這個會員被服務
served[vip] = true;
// 相當於這個人被插隊了，下一個還是處理他，所以 i不變
}
}
// 普通桌子
} else {
// 這個人是普通人就分配給他，
if (!player[i].isvip) {
AssignTableForPlayer(index, i);
// 然後處理下一個人，所以 i++
i++;
// 這個人是會員，並且沒被服務過，
} else if (!served[i]) {
// 先看所有給會員預留的桌子是否有空閑，有就給他，沒有就把這個普通桌子給他
// 找到所有會員桌中最早結束的那個
int t_vip = -1, t_vip_min_end = INT_MAX;
for (int j = 1; j <= k; ++j) {
if (table[j].isvip && table[j].end_time < t_vip_min_end) {
t_vip = j;
t_vip_min_end = table[j].end_time;
}
}
// 最早結束的會員桌在他來之前服務完了，說明有可用的會員桌，分配給他
if (t_vip != -1 && table[t_vip].end_time <= player[i].arrive_time) {
AssignTableForPlayer(t_vip, i);
// 標記這個會員被服務
served[i] = true;
// 然後處理下一個人，所以 i++
i++;
} else {
// 沒有可用的會員桌，就把當前這個普通桌子給他
AssignTableForPlayer(index, i);
// 標記這個會員被服務
served[i] = true;
// 然後處理下一個人，所以 i++
i++;
}
// 這個人是會員但是被服務過了就直接處理下一個
} else {
i++;
}
}
}
// 處理完所有玩家，按照被服務的開始時間排序
sort(player.begin(), player.end(), cmp2);
// 輸出結果，無法被服務的自動排除
for (auto it : player) {
if (it.start_time >= club_close_time)
continue;
// 到達時間
printf("%02d:%02d:%02d ", it.arrive_time / 3600,
it.arrive_time % 3600 / 60, it.arrive_time % 60);
// 被服務時間
printf("%02d:%02d:%02d ", it.start_time / 3600,
it.start_time % 3600 / 60, it.start_time % 60);
// 等待時間
printf("%.0f\n", round((it.start_time - it.arrive_time) / 60.0));
}
// 每個桌子服務了幾個人
printf("%d", table[1].serve_count);
for (int i = 2; i <= k; ++i)
printf(" %d", table[i].serve_count);
return 0;
}
說實在的，這個題，只要分類討論細節想到位了，真的不難！想不到位就多想想唄，把我這個部落格多看幾遍你絕對明白！啊哈哈哈！
