PAT甲级1026. Table Tennis
题意：
乒乓球俱乐部有N张桌子供公众使用。表的编号从1到N.对于任何一对玩家，如果有一些表在到达时打开，它们将被分配给具有最小数字的可用表。如果所有的表被占用，他们将不得不等待排队。
假设每对玩家可以玩2个小时以上。
你的工作是计算每个人在排队等候的时间，并为每个表中的一天中提供的玩家数量。
有一件事使得这个程序有点复杂，俱乐部为他们的VIP会员保留了一些表。当VIP桌子打开时，
队列中的第一个VIP对将拥有该权限。然而，如果队列中没有VIP，下一对玩家可以接受。另一方面，如果是VIP对的轮到，但没有VIP表可用，则可以作为任何普通玩家分配。
输入规格：
每个输入文件包含一个测试用例。
对于每种情况，第一行包含整数N（<= 10000） - 玩家对的总数。然后N行跟随，每个包含2次和一个VIP标签：HH：MM：SS - 到达时间，P - 一对玩家的播放时间（分钟），标签 - 如果持有VIP卡，则为1，或如果没有，则为0。
保证在俱乐部开放时到达时间为08:00:00至21:00:00。假设没有两个客户同时到达。按照玩家的信息，有2个正整数：K（<= 100） - 表的数量，M（<K） - VIP表的数量。最后一行包含M表号。
输出规格：
对于每个测试用例，首先按样品显示的格式打印每对玩家的到达时间，服务时间和等待时间。然后在一行中打印每张桌子所服务的玩家人数。请注意，输出必须按服务时间的时间顺序列出。
等待时间必须舍入到整数分钟。如果在关闭时间之前无法获取桌面，则不得打印其信息。
思路：
sick! sick problem! 我一开始比较年轻，把所有的时间用string来算。最后一个就是超时。皮水。转化成秒来算就行了。感觉问题点比较多。模拟排队。这个vip好烦。花了我好多时间。
- vip在普通table和viptable共存会选择viptable不管序号大小
- 超过两个小时按两个小时算
It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open.
虽然这么说，但还是有不合法输入?很皮。很smart。
- 超过21：00或者21：00：00都不给服务。
有个vip搞得比较乱。要一点一点分类。分类方法大概就是
//非会员，从从小到大寻找能用的table，找到break，没找到记录最快结束的table
//最快的table不是会员table,计算 ending / number 二级排序
//如果是会员table，向后搜索，结束之前没有会员来，计算，有会员来，swap。计算。
//会员，寻找最小能用的会员table，找到break,没找到记录最快结束的table
//最快结束的table按 ending / isviptable /number 三级排序
贴一点测试数据。
2
10:00:00 30 1
12:00:00 30 1
5 1
3
2
18:00:00 180 1
20:00:00 60 1
1 1
1
1
21:00:00 80 1
1 1
1
1
00:00:00 80 1
1 1
1
3
20:59:59 1 0
21:05:00 80 1
19:00:59 119 0
1 1
1
ac代码：
C++
// pat1026.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
#include<unordered_map>
#include<unordered_set>
using namespace std;
struct custom
{
int arriving;
int ending;
int playingtime;
int vip;
int wait;
int turn;
};
struct tab
{
int ending;
int vip;
};
int tablecount[105];
custom cus[10005];
tab q[105];
static bool cuscmp(custom& a, custom& b)
{
return a.arriving < b.arriving;
}
int main()
{
int n, k, m, viptable;
cin >> n;
//custom cus[10005];
int hour, minute, second;
for (int i = 0; i < n; i++)
{
scanf("%d:%d:%d %d %d", &hour, &minute, &second, &cus[i].playingtime, &cus[i].vip);
cus[i].arriving = hour * 60 * 60 + minute * 60 + second;
cus[i] .playingtime *= 60;
if (cus[i].playingtime > 7200) cus[i].playingtime = 7200;
//cus[i] = c;
}
cin >> k >> m;
//vector数组模拟table
//tab q[105];
//初始化table
for (int i = 0; i < k; i++)
{
q[i].ending = 28800;
q[i].vip = 0;
}
//插入vip的table到set中
for (int i = 0; i < m; i++)
{
cin >> viptable;
q[viptable - 1].vip = 1;
}
//vector<int> tablecount(k, 0); //记录table使用次数的计数器
int pos, last_min_table, last_min_ending;
for (pos = 0; pos < n; pos++)
{
//sort(cus.begin() + pos, cus.end(), cuscmp);
sort(cus + pos, cus + n, cuscmp);
if (cus[pos].arriving >= 75600) break;
//非会员，从从小到大寻找能用的table，找到break，没找到记录最快结束的table
//最快的table不是会员table,计算 ending / number 二级排序
//如果是会员table，向后搜索，结束之前没有会员来，计算，有会员来，swap。计算。
//会员，寻找最小能用的会员table，找到break,没找到记录最快结束的table
//最快结束的table按 ending / isviptable /number 三级排序
last_min_ending = 75600;
last_min_table = -1;
bool flag = true;
if (cus[pos].vip == 0) //非会员
{
for (int i = 0; i < k; i++)
{
if (q[i].ending >= 75600) continue;
if (cus[pos].arriving >= q[i].ending)
{
last_min_table = i;
last_min_ending = q[i].ending = cus[pos].arriving;
break;
}
else if (cus[pos].arriving < q[i].ending && q[i].ending < last_min_ending)
{
last_min_ending = q[i].ending;
last_min_table = i;
}
}
if (q[last_min_table].vip == 1) //会员table
{
int j = pos + 1;
while (j < n && cus[j].arriving <= q[last_min_table].ending)
{
if (cus[j].vip == 1)
{
swap(cus[j], cus[pos]);
break;
}
j++;
}
}
}
else //会员
{
for (int i = 0; i < k; i++)
{
if (q[i].ending >= 75600) continue;
if (cus[pos].arriving >= q[i].ending && (q[i].vip == 1 || last_min_ending != cus[pos].arriving))
{
last_min_table = i;
last_min_ending = q[i].ending = cus[pos].arriving;
if (q[i].vip == 1) break;
}
else if (cus[pos].arriving < q[i].ending)
{
if (q[i].ending < last_min_ending || q[i].ending == last_min_ending && q[i].vip == 1)
{
last_min_ending = q[i].ending;
last_min_table = i;
}
}
}
}
if (last_min_ending >= 75600) break;
tablecount[last_min_table]++;
cus[pos].wait = last_min_ending - cus[pos].arriving;
cus[pos].turn = last_min_ending;
q[last_min_table].ending = cus[pos].turn + cus[pos].playingtime;
}
int waittime;
for (int i = 0; i < pos; i++)
{
waittime = cus[i].wait / 60 + (cus[i].wait % 60 < 30 ? 0 : 1);
printf("%02d:%02d:%02d %02d:%02d:%02d %d
", cus[i].arriving / 3600, (cus[i].arriving % 3600) / 60, cus[i].arriving % 60,
cus[i].turn / 3600, (cus[i].turn % 3600) / 60, cus[i].turn % 60, waittime);
}
for (int i = 0; i < k - 1; i++)
{
cout << tablecount[i] << " ";
}
cout << tablecount[k - 1] << endl;
return 0;
}