题目链接
k张桌子，玩家到达后总是选择编号最小的桌子，且最多玩2h。 k张桌子中m张是vip桌，如果vip桌子有空闲，而且队列里面有vip成员，那么等待队列中的第一个vip球员会到最小的vip球桌训练。如果vip桌子空闲但是没有vip来，那么就分配给普通的人。如果没有vip球桌空闲，那么vip球员就当作普通人处理，也就是先来先服务。
现在给出每个球员的到达时间、要玩多久、是不是vip（是为1不是为0）。给出球桌数和所有vip球桌的编号，求出在关门前所有得到桌子的球员的到达时间、训练开始时间、等待时长（取整数，四舍五入），营业时间为8点到21点。如果在21:00 之前没有排的上队，那么就不需要服务。

细节问题：

• 21:00之前没有排上队，所有ser<13*3600才可以
• 训练时间超过2h的要压缩成2h
• 当有多个桌子空闲时，且空闲的里面有vip桌时，vip用户会选择编号最小的vip桌，即使有空闲的、编号更小的普通桌。如果空闲的里面没有vip桌，vip用户选择编号最小的桌
• 这题与一般队列题的区别在于队列是不连续的，即可能出现窗口空着，但是队列不在的情况，所以每次找桌子，不能找预计时间最小的，而是判断桌子是否空闲

原解

思路：将所有player按到达时间排序，每次找到当前空闲的桌子，如果是VIP桌子，看能否找到第一个等待的VIP客户，否则处理队首player。如果不是VIP桌子，处理队首player。处理队首player注意player是否需要等待，更新每个桌子当前结束时间。

• 对于VIP桌子且有VIP客户的情况，记得i–，否则就会跳过队首元素
• 寻找队列中VIP客户时，注意限制j<n，否则可能会有段错误，每个数组下标循环时，不管会不会超出上限，都先写上

下面这个是24分的答案，测试点3.5.7出错，不满足最后一个条件和队列不连续的条件

#include<iostream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define N 10005
struct player{
    int arr,ser,p,wait,tag,flag;
}play[N];
int w[105],VIP[105],cnt[105];
bool cmp1(const player& a,const player& b){
    return a.arr<b.arr;
}
bool cmp2(const player& a,const player& b){
    if(a.flag!=b.flag) return a.flag>b.flag;
    return a.ser<b.ser;
}
int n,k,m;
const int ed=13*3600;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int h,m,s,p;
        scanf("%d:%d:%d",&h,&m,&s);
        cin>>p;
        play[i].arr=(h-8)*3600+m*60+s;
        if(p>120) p=120;
        play[i].p=p*60;
        cin>>play[i].tag;
        play[i].flag=0;
    }
    cin>>k>>m;
    while(m--){
        int idx;cin>>idx;
        VIP[idx]++;
    }
    sort(play,play+n,cmp1);
    for(int i=0;i<n;i++){
        if(play[i].flag==1) continue;
        int u=0,min=ed; //找到空闲的最小桌子
        for(int j=1;j<=k;j++)
            if(w[j]<min)
                min=w[j],u=j;
        if(u==0) break;  //不能在21:00前开始
        else {
            if(VIP[u]!=0){//VIP table
                int v=-1;
                for(int j=i;w[u]>=play[j].arr&&j<n;j++){
                    if(play[j].tag==1&&play[j].flag==0){
                        cnt[u]++;v=j;
                        play[j].ser=w[u];
                        play[j].flag=1;
                        play[j].wait=round((double)(w[u]-play[j].arr)/60);
                        w[u]+=play[j].p;
                        i--;
                        break;
                    }
                }
                if(v==-1){//没有在排队的VIP客户
                    cnt[u]++;
                    play[i].flag=1;
                    if(w[u]<=play[i].arr){ //队头不需要等待
                        play[i].wait=0;
                        play[i].ser=play[i].arr;
                        w[u]=play[i].arr+play[i].p;
                    }
                    else{ //队头需要等待
                        play[i].wait=round((double)(w[u]-play[i].arr)/60);
                        play[i].ser=w[u];
                        w[u]+=play[i].p;                       
                    }
                }
            }
            else{
                cnt[u]++;
                play[i].flag=1;
                if(w[u]<=play[i].arr){ 
                    play[i].wait=0;
                    play[i].ser=play[i].arr;
                    w[u]=play[i].arr+play[i].p;
                }
                else{
                    play[i].wait=round((double)(w[u]-play[i].arr)/60);
                    play[i].ser=w[u];
                    w[u]+=play[i].p;
                }
            }
        } 
    }
    sort(play,play+n,cmp2);
    for(int i=0;i<n;i++){
        if(play[i].flag==0) break;
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",
        play[i].arr/3600+8,play[i].arr%3600/60,play[i].arr%60,
        play[i].ser/3600+8,play[i].ser%3600/60,play[i].ser%60,play[i].wait);
    }
    for(int i=1;i<=k;i++){
        if(i!=1) cout<<' ';
        cout<<cnt[i];
    }
    return 0;
}

正解

分析与代码

#include<bits/stdc++.h>
using namespace std;
struct person{
    int arrive,use,start;           //玩家对的到达时间，使用持续时间，开始使用时间
    bool served,vip;                //玩家对是否被服务过（F代表未使用过桌子），玩家对是否为vip
};
int cmp1(person &a,person &b){
    return a.arrive<b.arrive;       //玩家对按到达时间顺序升序
}
int cmp2(person &a,person &b){
    return a.start<b.start;         //服务过的玩家按开始使用时间升序
}
struct table{
    int endtime,cnt;                //桌子的结束使用时间（即何时空闲出来），桌子服务玩家对数量
    bool vip;                       //桌子是否为vip
};
vector<person> r;                   //玩家对序列，需按到达时间顺序来排序
vector<table> t;                    //桌子序列

int findvip(int index,int before){
    for(int i=index;i<r.size() && r[i].arrive<=before;i++){
        if(!r[i].served && r[i].vip)
            return i;
    }
    return -1;
}

void update(int personId,int tableId){
    r[personId].start=max(r[personId].arrive,t[tableId].endtime);
    r[personId].served=1;
    t[tableId].endtime=r[personId].start+r[personId].use;
    t[tableId].cnt++;
}
 
int main(){
    int n,m,k,tmpid;
    scanf("%d",&n);
    //初始化玩家对的信息，并排序
    for(int i=0;i<n;i++){
        int h,m,s,use,vip,arrive;
        scanf("%d:%d:%d %d %d",&h,&m,&s,&use,&vip);
        arrive=h*3600+m*60+s;
        use=use>120?7200:use*60;
        r.push_back({arrive,use,0,0,vip>0});
    }
    sort(r.begin(),r.end(),cmp1);
    //初始化桌子的信息
    scanf("%d %d",&m,&k);
    for(int i=0;i<m;i++)
        t.push_back({28800,0,0});
    for(int i=0;i<k;i++){
        scanf("%d",&tmpid);
        t[tmpid-1].vip=1;
    }
    for(int i=0;i<r.size();){
        //找到最先空闲的桌子,如果多个桌子同时空闲，则返回桌子号最小的那个
        int minEndTime=INT_MAX,minEndIndex;
        for(int j=0;j<m;j++){
            if(minEndTime>t[j].endtime){
                minEndTime=t[j].endtime;
                minEndIndex=j;
            }
        }
        //如果最先空闲的桌子空闲的太晚了，或者当前序列中的第一位玩家对达到的时间太晚了，就退出循环
        if(minEndTime>=75600 || r[i].arrive>=75600)
            break;
        //声明新的变量，personId为经过调整选择后最终的开始使用桌子的玩家对索引，tableId为为经过调整选择后最终的开始被使用的桌子
        int personId=i, tableId=minEndIndex;
        //如果当前的最早空闲且号最小的桌子空闲时，存在玩家对已经在等待了
        if(minEndTime>=r[i].arrive){
            //并且当前的最早空闲且号最小的桌子是vip，寻找是vip的且未服务过的，玩家对到达时间不晚于minEndTime的玩家对索引
            if(t[tableId].vip){
                int vipid=findvip(personId,minEndTime);
                personId=vipid!=-1?vipid:personId;
            }else if(r[i].vip){ //虽然当前的最早空闲且号最小的桌子不是vip，但是还可能存在同时空闲，桌号更大的桌子是vip
                for(int j=0;j<m;j++){
                    if(t[j].vip && t[j].endtime<=r[personId].arrive){
                        tableId=j;
                        break;
                    }
                }
            }
        }else{
            for(int j=0;j<m;j++){           //从该行起的总共5行代码被注释掉仍能通过所有的测例，说明测例不够完善
                if(t[j].endtime<=r[personId].arrive){
                    tableId=j;
                    break;
                }
            }
            if(r[personId].vip){
                for(int j=0;j<m;j++){       //尝试寻找空闲的vip桌子并调整tableId，顺序找到即退出得到的就是号码最小的
                    if(t[j].vip && t[j].endtime<=r[personId].arrive){
                        tableId=j;
                        break;
                    }
                }
            }
        }
        update(personId,tableId);
        //别忘了更新玩家对的遍历索引
        while(i<r.size() && r[i].served)++i;
    }
    //按要求输出被服务过的玩家对
    sort(r.begin(),r.end(),cmp2);
    for(int i=0;i<r.size();i++){
        if(r[i].served){
            int wait=r[i].start-r[i].arrive;
            printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",r[i].arrive/3600,r[i].arrive%3600/60,r[i].arrive%60,\
                   r[i].start/3600,r[i].start%3600/60,r[i].start%60,(int)(1.0*wait/60+0.5));
        }
    }
    for(int i=0;i<m;i++)
        printf("%d%c",t[i].cnt,i==m-1?'\n':' ');
    return 0;
}