1026 Table Tennis

Sample Input:

10
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 30 0
08:12:00 10 1
20:40:00 13 0
08:01:30 15 1
20:53:00 10 1
20:54:00 10 0
3 1
2

Sample Output:

08:00:00 08:00:00 0
08:01:30 08:01:30 0
08:02:00 08:02:00 0
08:12:00 08:16:30 5
08:10:00 08:20:00 10
20:40:00 20:40:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
20:53:00 20:53:00 0
4 3 2

题目大意

桌球俱乐部有N张桌子，其中有M张是VIP桌子。对于所有普通的桌子，先到先得。对于VIP桌子，VIP人员有特殊待遇，但如果在场无等待游玩的VIP人员，VIP桌子可为普通人员服务。但如果排队等待的人员中，有VIP人员，VIP桌子优先提供给最先抵达的VIP人员。

注意 : VIP人员优先使用VIP桌子，但如果他抵达时，VIP桌子没有空，但普通桌子有空，其亦可正常排队，去使用普通桌子。

求每个人开始游玩的时间，和等待时间，最后输出每桌服务的人数

思路

为人员建立一个数据结构，ed[n]表示窗口n最后结束工作的时间

setvip，记录VIP窗口的编号，对VIP窗口的使用进行分类讨论即可

C/C++ 

#include
using namespace std;
struct Player{
    int arrive,start,play,vip;
}p;
set<int> vip;
vector line[2],all;
int ed[101]={999999},nums[101],edNum,N;
bool cmp1(Player x,Player y){ return x.arrive>y.arrive; }
Player earlyArrive();
bool  findTable();
int main()
{
    int a,b,c;
    cin >> N;
    while (N--){
        scanf("%d:%d:%d %d %d", &a, &b, &c, &p.play, &p.vip);
        p.arrive = a * 3600 + b * 60 + c;
        if (p.arrive >= 75600) continue;
        if (p.play > 120) p.play = 120;
        line[p.vip].push_back(p);
    }
    cin >> edNum >> N;
    while (N--){
        cin >> a;
        vip.insert(a);
    }
    sort(line[0].begin(),line[0].end(), cmp1);
    sort(line[1].begin(),line[1].end(), cmp1);
    while (!line[0].empty() || !line[1].empty()){
        p = earlyArrive();
        if(!findTable()) break;
    }
    for(Player x:all){
        int num1 = x.arrive,num2 = x.start;
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",num1/3600,num1%3600/60,num1%60,num2/3600,num2%3600/60,num2%60,(num2-num1+30)/60);
    }
    cout << nums[1];
    for(int z=2;z<=edNum;z++) cout << " " << nums[z];
    return 0;
}
bool findTable()
{
    if(p.vip==1){ // vip优先匹配VIP窗口
        for(int x:vip){
            if(ed[x]<=p.arrive){
                p.start = p.arrive;
                ed[x] = p.arrive + p.play*60;
                all.push_back(p);
                line[1].pop_back();
                nums[x]++;
                return true;
            }
        }
    }
    int flag = 0; // 找到该人抵达时，已经完成工作的最小编号窗口
    for(int z=1;z<=edNum;z++){
        if(ed[z]
            flag = z;
            break;
        }
    }
    if(flag==0) for(int z=1;z<=edNum;z++) if(ed[z]// 该人抵达时,没有空窗口,那就寻找最先结束的窗口
    if(ed[flag]>=75600) return false;
    for(int x:vip){
        if(line[1].empty()) break;
        if(flag==x){
            if(ed[flag]>=line[1].back().arrive) p = line[1].back();
            break;
        }
    }
    nums[flag]++;
    if(ed[flag]<=p.arrive){
        p.start = p.arrive;
        ed[flag] = p.arrive + p.play*60;
    }else{
        p.start = ed[flag];
        ed[flag] += p.play*60;
    }
    all.push_back(p);
    line[p.vip].pop_back();
    return true;
}
Player earlyArrive()
{
    if(line[1].empty() || (!line[0].empty() && line[1].back().arrive > line[0].back().arrive)) return line[0].back();
    return line[1].back();
}