1.整体思路为：先遍历vip桌子和vip玩家，如果有匹配成功的，进行匹配；然后再遍历一轮所有的桌子和等候的玩家，有匹配的进行匹配；
2.被卡的地方：
1）关于秒的四舍五入，是按照大于等于30秒，进一分钟，小于30秒则舍去的原则；最后的一个测试用例就是检验这个30秒的
2）在遍历所有的玩家时，由于可能存在已经被前面服务了的vip玩家，所以需要额外加一个处理，使得playIndex指向的是未被服务的玩家；
3）主要是忘记了遍历vip玩家时，同样存在2）中的问题，因为在遍历所有玩家的时候，有可能vip玩家也被服务安排了，所以需要在遍历vip玩家中加一个处理，使得vipIndex指向未被服务的vip玩家。
3.下面是一些比较重要的测试用例：
//边缘测试例子 1 21:00:00 10 1 3 3 1 2 3 1 20:59:59 10 1 3 3 1 2 3 0 3 1 2 //vip桌子分配例子，有vip桌子时，优先把vip分到编号小的vip桌子，而不是编号小的vip桌子 4 06:00:00 30 1 08:00:00 30 1 10:00:00 30 1 12:00:00 30 1 5 1 3 答案为： 06:00:00 08:00:00 120 08:00:00 08:00:00 0 10:00:00 10:00:00 0 12:00:00 12:00:00 0 1 0 3 0 0 //超过两小时的例子 2 18:00:00 180 1 20:00:00 60 1 1 1 1 答案为： 18:00:00 18:00:00 0 20:00:00 20:00:00 0 2 //关于四舍五入为1分钟的例子，大约等于30秒才+1分钟，小于30则不+ 3 07:59:31 60 1 07:59:29 60 1 08:00:30 100 1 2 1 1 答案为： 1 07:59:29 08:00:00 1 07:59:31 08:00:00 0 08:00:30 09:00:00 60 2 1
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
AC代码：
//#include<string>
//#include <iomanip>
#include<vector>
#include <algorithm>
//#include<stack>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
using namespace std;
#define maxServe 46810
/*
//正常的检测例子，全部为普通玩家
9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:29 5 0
08:12:00 10 0
20:50:00 10 0
08:01:30 15 0
20:53:00 10 0
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:10:29 08:16:30 6
08:12:00 08:20:00 8
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 table
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 0
答案为：
08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:10:00 08:16:30 7
08:12:00 08:20:00 8
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和viptable
9
20:52:00 10 0
07:59:59 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
答案为：
07:59:59 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
//边缘测试例子
1
21:00:00 10 1
3 3
1 2 3
1
20:59:59 10 1
3 3
1 2 3
0
3 1
2
//vip桌子分配例子，有vip桌子时，优先把vip分到编号小的vip桌子，而不是编号小的vip桌子
4
06:00:00 30 1
08:00:00 30 1
10:00:00 30 1
12:00:00 30 1
5 1
3
答案为：
06:00:00 08:00:00 120
08:00:00 08:00:00 0
10:00:00 10:00:00 0
12:00:00 12:00:00 0
1 0 3 0 0
//超过两小时的例子
2
18:00:00 180 1
20:00:00 60 1
1 1
1
答案为：
18:00:00 18:00:00 0
20:00:00 20:00:00 0
2
//关于四舍五入为1分钟的例子，大约等于30秒才+1分钟，小于30则不+
3
07:59:31 60 1
07:59:29 60 1
08:00:30 100 1
2 1
1
答案为：
1
07:59:29 08:00:00 1
07:59:31 08:00:00 0
08:00:30 09:00:00 60
2 1
*/
string int2str(int a)
{
char n = a / 10 + '0';
char m = a % 10 + '0';
string tmp = "";
tmp += n;
tmp += m;
return tmp;
}
int char2int(char a)
{
int tmp = a - '0';
return tmp;
}
int time2int(string a)
{
int hour = char2int(a[0]) * 10 + char2int(a[1]) - 8;
int min = char2int(a[3]) * 10 + char2int(a[4]);
int sec = char2int(a[6]) * 10 + char2int(a[7]);
return hour * 3600 + min * 60 + sec;
}
struct playerNode{
string arrive;
int playTime, waitTime, serve;
bool isVip;
string serveStr();
int waitInt();
int serveTableNum;
playerNode() :arrive(""), serve(maxServe), playTime(0), waitTime(0), isVip(false){};
playerNode(string a, int p, bool v) :arrive(a), serve(maxServe), playTime(p), waitTime(0), isVip(v){};
};
string playerNode::serveStr()
{
int hour = serve / 3600;
int min = (serve - hour * 3600) / 60;
int sec = serve % 60;
return int2str(hour + 8) + ":" + int2str(min) + ":" + int2str(sec);
}
int playerNode::waitInt()
{
int diff = serve - time2int(arrive);
int min = diff / 60;
if (diff % 60 >= 30)
min++;
return min;
}
struct tableNode{
bool isVip;
int playIndex;//当前玩家index
int serveNum;//已经服务的玩家数量
tableNode() :isVip(false), playIndex(-1), serveNum(0) {};
};
bool cmp(const playerNode&a, const playerNode&b)
{
return a.arrive < b.arrive;
}
bool cmp2(const playerNode&a, const playerNode&b)
{//按照服务时间排序
return a.serve < b.serve;
}
int main(void)
{
int playerNum;
cin >> playerNum;
vector<playerNode> player(playerNum);
vector<int> vipPlayer(0);
for (int i = 0; i < playerNum; i++)
{//输入玩家信息
string arrive;
int playTime;
bool isVip;
cin >> arrive >> playTime >> isVip;
if (playTime > 120)
playTime = 120;
playTime *= 60;
player[i].arrive = arrive;
player[i].playTime = playTime;
player[i].isVip = isVip;
}
sort(player.begin(), player.end(), cmp);
for (int i = 0; i < playerNum; i++)
{//建立vip队列
if (player[i].isVip) vipPlayer.push_back(i);
}
int tableNum;
int vipTableNum;
cin >> tableNum >> vipTableNum;
vector<tableNode> table(tableNum);
vector<int> vipTable(0);
int vipIndex = 0;
int playerIndex = 0;
for (int i = 0; i < vipTableNum; i++)
{//输入vip桌子
int a;
cin >> a;
table[a - 1].isVip = true;
vipTable.push_back(a - 1);
}
for (int now = 0; now < 13 * 3600; now++)
{
for (int i = 0; i < table.size(); i++)
{//遍历所有桌子，处理正在玩的玩家
if (table[i].playIndex != -1)
{//桌子有人
player[table[i].playIndex].playTime--;
if (player[table[i].playIndex].playTime <= 0)
{//清空桌子
table[i].playIndex = -1;
}
}
}
if (vipIndex < vipPlayer.size())
{//先服务vip玩家
for (int j = 0; j < vipTable.size(); j++)
{
while (vipIndex < vipPlayer.size() && player[vipPlayer[vipIndex]].serve != maxServe)
{//跳过已经被服务的vip玩家，主要卡在这里
vipIndex++;
}
int i = vipTable[j];//用i表示vip桌子
if (table[i].playIndex == -1 && vipIndex < vipPlayer.size() && time2int(player[vipPlayer[vipIndex]].arrive) <= now)
{
table[i].serveNum++;
table[i].playIndex = vipPlayer[vipIndex];
player[vipPlayer[vipIndex]].serveTableNum = i;
player[vipPlayer[vipIndex]].serve = now;
vipIndex++;
}
}
}
if (playerIndex < player.size())
{//服务剩下的玩家,普通玩家和vip玩家混在一起
for (int i = 0; i < table.size(); i++)
{
while (playerIndex < player.size() && player[playerIndex].serve != maxServe)
{//确保当前playerIndex的玩家是没有被服务的
playerIndex++;
}
if (table[i].playIndex == -1 && playerIndex < player.size() && time2int(player[playerIndex].arrive) <= now)
{
table[i].serveNum++;
table[i].playIndex = playerIndex;
player[playerIndex].serveTableNum = i;
player[playerIndex].serve = now;
playerIndex++;
}
}
}
}
sort(player.begin(), player.end(), cmp2);
for (int i = 0; i < player.size(); i++)
{
if (player[i].serve != maxServe)
{
cout << player[i].arrive << " " << player[i].serveStr() << " " << player[i].waitInt() /*<< " " << player[i].serveTableNum*/ << endl;
}
}
for (int i = 0; i < table.size(); i++)
{
cout << table[i].serveNum;
if (i != table.size() - 1)
cout << " ";
}
return 0;
}
