[PAT解题报告] Table Tennis
超级麻烦的模拟题。
有乒乓球桌子，每个人来了要说玩多长时间。桌子有普通桌子和VIP桌子。可以认为普通人和VIP在两个不同的队列里，有空桌的话VIP优先，并且VIP优先进入VIP的桌子。还有一些限制每个人不能玩超过两个小时而且没有VIP的时候，普通人也可以用VIP的桌子，VIP如果没有VIP桌子可以用普通人的桌子——总之很多规则，最后看一下每个人玩多久，每个桌子支持了多少人。
我们用事件驱动的方法。
事件包括 ：
（1） 时间
（2） 人的id或者桌子的id
（3） 人的id表示人来了，桌子的id表示桌子腾空
我们看一下如何处理这些事件
我们把所有事件按照时间顺序排序，并且同一时间里优先考虑先来人，这样腾出桌子后，能使用这个桌子的人已经在等着呢。
（1） 腾空桌子比较简单
（1.1）把桌子加入到对应集合（VIP桌子和非VIP桌子）
（1.2）考虑是否能进人， 如果有VIP等并且有VIP的桌子，就给VIP分配VIP的桌子（编号最小的）
（1.3） 至此，要么没有VIP的桌子，要么没有VIP人，那么所有人“平等”分配桌子
（2） VIP人来
（2.1) 有VIP的桌子，就给他分配VIP的桌子
（2.2) 没有VIP的桌子，有普通的桌子，给他分配普通桌子
（2.3) 桌子全满，进入VIP等候队列
（3）普通人来
(3.1)
有空桌子（无论是否是VIP桌子）就分配给他——注意这是题目的坑所在，普通人只要有桌子，就可以分配给他一个编号最小的桌子，因为有空桌子一定没有人在等
(3.2) 进入普通的等候队列
关于(1.3)如何平等？
我们可以支持选一个来的最早的人，尽管有两种队列，我们从VIP人和普通人里选一个来得最早的就可以了——题目说没有两个人同时到
如何选一个编号最小的桌子？ 和选人一样，从两种桌子集合里面选一个最小的就可以了。
至于集合，可以用set<int>来做，begin就是最小的，我们可以存两种空桌子的id,
还有两种排队的人的id，注意存人的id，主要要存他什么时候来的，所以要存pair<int,int>
表示来的时间和id，因为第一维才是最重要的。
关于 分配桌子后事件的变化，
一个人被分配了一张桌子，我们知道他玩的时间，自然知道他离开桌子的时间，所以我们在事件队列里加一个腾空桌子的事件。总之，就是每满足一个人，就计算他离开的时间加入事件队列。
所以事件是动态的，需要动态按照时间顺序排序，所以自然就用堆、优先队列这种数据结构，我用了优先队列。
time, id, time表示时间,id和类型。如果类型是0，表示id是腾空桌子的id，否则type是1表示id是来的人的id。
还有一个坑就是每个人玩的时间不要超过两个小时——但是输入请求有超过两个小时的，我们需要自己把它变为两个小时（申请玩的时间和120分钟取最小值）。
代码很长： 关键还是要理解上述描述的，选人，选桌，处理时间，处理VIP的过程，理解起来就方便了。
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <set>
using namespace std;
const int N = 10004;
const int M = 102;
const int close = 3600 * 21;
struct node {
int time;
int id;
int type;
}; // type = 0, table free, 1 person come
bool operator<(const node &a,const node &b) {
if (a.time > b.time) {
return true;
}
if (a.time < b.time) {
return false;
}
return (a.time > b.time) || ((a.time == b.time) && (a.type < b.type));
}
int num[M];
int play[N];
bool isvipperson[N];
bool isviptable[M];
set<int> ordtable;
set<int> viptable;
set<pair<int,int> > vipperson;
set<pair<int,int> > ordperson;
priority_queue<node> affair;
int gettable() {
int r;
if (ordtable.empty()) {
r = *viptable.begin();
viptable.erase(viptable.begin());
return r;
}
if (viptable.empty()) {
r = *ordtable.begin();
ordtable.erase(ordtable.begin());
return r;
}
if (*ordtable.begin() < *viptable.begin()) {
r = *ordtable.begin();
ordtable.erase(ordtable.begin());
}
else {
r = *viptable.begin();
viptable.erase(viptable.begin());
}
return r;
}
pair<int,int> getperson() {
pair<int,int> r;
if (ordperson.empty()) {
r = *vipperson.begin();
vipperson.erase(vipperson.begin());
return r;
}
if (vipperson.empty()) {
r = *ordperson.begin();
ordperson.erase(ordperson.begin());
return r;
}
if (ordperson.begin()->first < vipperson.begin()->first) {
r = *ordperson.begin();
ordperson.erase(ordperson.begin());
}
else {
r = *vipperson.begin();
vipperson.erase(vipperson.begin());
}
return r;
}
void freetable(int x) {
if (isviptable[x]) {
viptable.insert(x);
}
else {
ordtable.insert(x);
}
}
void print(int x,int y) {
printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",x / 3600, x % 3600 / 60, x % 60, y / 3600, y % 3600 / 60, y % 60, (y - x + 30) / 60);
}
int main() {
int n;
node temp;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
int x;
int hh,mm,ss;
scanf("%d:%d:%d %d%d",&hh,&mm,&ss,&play[i],&x);
isvipperson[i] = x;
temp.id = i;
temp.time = hh * 3600 + mm * 60 + ss;
temp.type = 1;
play[i] = min(play[i], 120);
play[i] *= 60;
affair.push(temp);
}
int a;
for (scanf("%d%d",&n,&a);a;--a) {
int x;
scanf("%d",&x);
isviptable[--x] = true;
viptable.insert(x);
}
for (int i = 0; i < n; ++i) {
if (!isviptable[i]) {
ordtable.insert(i);
}
}
while (!affair.empty()) {
temp = affair.top();
affair.pop();
int now = temp.time;
if (now >= close) {
break;
}
if (temp.type == 0) {
freetable(temp.id);
while ((!affair.empty()) && (affair.top().type == 0) && (affair.top().time == now)) {
freetable(affair.top().id);
affair.pop();
}
while ((!viptable.empty()) && (!vipperson.empty())) {
temp.time = now + vipperson.begin()->second;
temp.type = 0;
++num[temp.id = *viptable.begin()];
print(vipperson.begin()->first, now);
affair.push(temp);
viptable.erase(viptable.begin());
vipperson.erase(vipperson.begin());
}
while (((!ordperson.empty()) || (!vipperson.empty())) && ((!ordtable.empty()) || (!viptable.empty()))) {
pair<int,int> g = getperson();
temp.time = now + g.second;
temp.type = 0;
++num[temp.id = gettable()];
print(g.first,now);
affair.push(temp);
}
}
else if (isvipperson[temp.id]) {
if (!viptable.empty()) {
temp.time = now + play[temp.id];
print(now, now);
temp.type = 0;
++num[temp.id = *viptable.begin()];
affair.push(temp);
viptable.erase(viptable.begin());
}
else if (!ordtable.empty()) {
temp.time = now + play[temp.id];
print(now, now);
temp.type = 0;
++num[temp.id = *ordtable.begin()];
affair.push(temp);
ordtable.erase(ordtable.begin());
}
else {
vipperson.insert(make_pair(now, play[temp.id]));
}
}
else if ((!viptable.empty()) || (!ordtable.empty())) {
temp.time = now + play[temp.id];
print(now, now);
temp.type = 0;
++num[temp.id = gettable()];
affair.push(temp);
}
else {
ordperson.insert(make_pair(now, play[temp.id]));
}
}
for (int i = 0; i < n; ++i) {
if (i) {
putchar(' ');
}
printf("%d",num[i]);
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1026
金山WPS公司福利 286人发布
