甲级PAT 1026 Table Tennis (30 分)（模拟+三大坑点总结）

【题意】

有一家乒乓球的店，营业时间为8:00-21:00。现在已知一天要接待的客户对数，每对客户的抵达时间、使用桌子时间和是否为VIP，然后是K张桌子，M张VIP桌和M张VIP桌的编号。要求按接待时间输出每对被服务的客户的抵达时间、开始服务时间和等待时间，然后输出每张桌子接待的客户的对数。

【题解】

需要注意的是：

①所有的客户的抵达时间在8:00-21:00没错，但是只有当开始服务时间早于21:00时才会被接待，需要输出信息。

②当客户的使用时间超过2小时，按两小时算，因为最多使用两小时。

③当有空闲的VIP桌子和普通桌子时，VIP用户首先优先选择VIP桌，再选择编号小的。当只有空闲的普通桌子时，VIP客户和普通客户都优先选择编号最小的空闲桌子。

④等待时间按分钟四舍五入(也有可能是因为我读错以为向上取整所以觉得坑)。

然后按题意慢慢模拟即可。

【代码】

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct p{
    int date,t,is,ser=0;
}f[10005];
bool cmp(p a,p b){
    return a.date<b.date;
}
bool cmp2(p a,p b){
    return a.ser<b.ser;
}
int sta[105]={0};
int c[105]={0};
int vis[105]={0};
queue <int> q[3];
int main()
{
    int n; scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int h,m,s;
        scanf("%d:%d:%d %d %d",&h,&m,&s,&f[i].t,&f[i].is);
        f[i].date=h*60*60+m*60+s;
        f[i].t=min(f[i].t*60,2*60*60);
    }
    sort(f+1,f+n+1,cmp);
    int k,m; scanf("%d%d",&k,&m);
    while(m--){
        int x; scanf("%d",&x);
        sta[x]=1; //VIP桌
    }
    int pos=1,a[3]={0};
    for(int i=8*60*60;i<21*60*60;i++){
        if(pos<=n&&f[pos].date==i) q[f[pos].is].push(pos),pos++; //客户抵达，压入等待序列
        if(!q[0].empty()) a[0]=q[0].front(); //普通
        if(!q[1].empty()) a[1]=q[1].front(); //VIP
        queue <int> v; while(!v.empty()) v.pop(); //记录空闲的VIP桌
        for(int j=1;j<=k;j++){ //遍历每张桌子
            if(vis[j]&&f[vis[j]].ser+f[vis[j]].t==i) vis[j]=0; //服务完成，变成空闲
            if(!vis[j]&&sta[j]) v.push(j);
        }
        while(!q[1].empty()&&!v.empty()){ //优先匹配VIP客户和VIP桌
            q[1].pop();
            int num=v.front(); v.pop();
            vis[num]=a[1];
            c[num]++;
            f[a[1]].ser=i;
            if(!q[1].empty()) a[1]=q[1].front();
            else a[1]=0;
        }
        for(int j=1;j<=k;j++){
            if(!vis[j]){ //可用
                if(!a[0]&&!a[1]) continue;
                int op=0;
                if(a[1]&&(!a[0]||f[a[1]].date<f[a[0]].date)) op=1;
                q[op].pop();
                vis[j]=a[op];
                f[a[op]].ser=i;
                if(!q[op].empty()) a[op]=q[op].front();
                else a[op]=0;
                c[j]++;
            }
        }
    }
    sort(f+1,f+n+1,cmp2);
    int i=1;
    while(f[i].ser==0&&i<=n) i++;
    for(;i<=n;i++)
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",f[i].date/3600,f[i].date%3600/60,f[i].date%60,f[i].ser/3600,f[i].ser%3600/60,f[i].ser%60,(f[i].ser-f[i].date+30)/60);
    for(int i=1;i<=k;i++)
        printf(i<k?"%d ":"%d\n",c[i]);
    return 0;
}