PAT 甲级 1026 Table Tennis (30 分)（坑点很多，逻辑较复杂，做了1天）

#include<bits/stdc++.h>
using namespace std;
struct node{
int a;//到达的时间
int s;//开始的时间
int t;//服务时间 };
struct cmp
{
bool operator()(node &x,node &y)
{
return x.a > y.a;
}
};
struct cmp2
{
bool operator()(node &x,node &y)
{
return x.s > y.s;
}
};
priority_queue<node ,vector<node>,cmp>a,b;//a为普通用户，b为vip用户
priority_queue<node ,vector<node>,cmp2>ans;
int n,m,k;
int tab[];//桌子服务的人数
int vt[];//标记是不是vip桌子
node q[];//正在服务的人们
int main(){
cin>>n;
memset(vt,,sizeof(vt));
memset(tab,,sizeof(tab));
while(!a.empty()) a.pop();
while(!b.empty()) b.pop();
while(!ans.empty()) ans.pop();
for(int i=;i<=n;i++){
int hh,mm,ss;
node x;
scanf("%d:%d:%d",&hh,&mm,&ss);
hh=hh*+mm*+ss;
cin>>mm;
mm*=;
if(mm>*) mm=*;
x.a=hh;
x.t=mm;
int v;
cin>>v;
if(x.a>=*){//时间超过来的直接不要
continue;
}
if(v==){
a.push(x);
}else{//vip
b.push(x);
}
}
cin>>k>>m;
for(int i=;i<=k;i++){//初始化
q[i].a=-;//初始来的人时间为-1
q[i].s=*;
q[i].t=;
}
for(int i=;i<=m;i++){
int x;
cin>>x;
vt[x]=;
}
while(!a.empty() || !b.empty())//开始执行
{
int min_t=;//找到一个最早的结束时间
int min_k=-;//最早结束时间对于的桌号
for(int i=;i<=k;i++){
if(min_t>q[i].s+q[i].t){
min_t=q[i].s+q[i].t;
min_k=i;
}
}
if(min_t>=*){
break;
}
//【1】先检查是不是vip桌子
if(vt[min_k]){
if(!b.empty()){//先看看队列里有没有vip
node x=b.top();
if(x.a<min_t){//如果vip在队列里，优先考虑
ans.push(q[min_k]);//把排在min_k的人放进最终答案中
q[min_k].a=x.a;
q[min_k].t=x.t;
q[min_k].s=min_t;
tab[min_k]++;//对于桌子服务的人数++
b.pop();
continue;
}
}
}
//【2】不是vip桌子
node x,y;
if(!a.empty()){
x=a.top();
}else{//小技巧，空的话就99999999
x.a=;
}
if(!b.empty()){
y=b.top();
}else{
y.a=;
}
if(x.a<y.a){//两者谁先就放谁
ans.push(q[min_k]);
tab[min_k]++;
q[min_k].a=x.a;
q[min_k].t=x.t;
a.pop();
if(x.a<min_t){
q[min_k].s=min_t;
}else{
q[min_k].s=x.a;
}
}else{//如果是vip早的话，看看有没有同样结束的vip桌子
//(1)坑点！优先把vip分到编号小的vip桌子，而不是编号小的桌子
int flag=;
for(int j=;j<=k;j++){
if(vt[j] && y.a >= q[j].s+q[j].t){//有符合条件的桌子
ans.push(q[j]);
tab[j]++;
q[j].a=y.a;
q[j].t=y.t;
q[j].s=y.a;
b.pop();
flag=;
break;
}
}
if(flag) continue;
//(2) 否则，就放在min_k这张桌子上
ans.push(q[min_k]);
tab[min_k]++;
q[min_k].a=y.a;
q[min_k].t=y.t;
b.pop();
if(y.a<min_t){
q[min_k].s=min_t;
}else{
q[min_k].s=y.a;
}
}
}
for(int i=;i<=k;i++){
ans.push(q[i]);
}
//输出
while(!ans.empty()){
node x = ans.top();
ans.pop(); if(x.a==-){//一开始是默认没有人的
continue;
}
int cha=x.s-x.a;//计算时间差 int hh=x.a/;
x.a=x.a%;
int mm=x.a/;
int ss=x.a%;
printf("%02d:%02d:%02d ",hh,mm,ss); hh=x.s/;
x.s=x.s%;
mm=x.s/;
ss=x.s%;
printf("%02d:%02d:%02d ",hh,mm,ss); cout<<int(cha*1.0/+0.5)<<endl;//四舍五入,不是向上取整
}
for(int i=;i<=k;i++){
cout<<tab[i];
if(i!=k) cout<<" ";
}
return ;
}