PAT [1026] TableTennis (30)

一个乒乓球俱乐部有N张桌子可供公众使用。这些表从1到n被编号为任意一对，如果有一些球台在它们到达时是空的，它们将被分配到可用的最小编号的球台上。如果所有的表都被占用，它们将不得不在队列中等待。假设每一对球员最多能踢2个小时。
你的任务是计算排队等待时间的每个人，以及每一张桌子上的玩家的数量。
让这个过程有点复杂的一点是，俱乐部为他们的VIP成员保留了一些桌子。当VIP桌字空闲时，排在队伍中的第一对贵宾将会有特权。然而，如果队伍中没有贵宾，那么普通队员就可以接受。另一方面，如果有VIP但是没有VIP桌子，那么VIP就作为普通队员看待。

输入

对于每一种情况，第一行包含一个整数N(小于=10000)-玩家总数的总数。然后N行，每一个都包含2次和VIP标签:HH:MM:到达时间，P-在几分钟的时间里玩的时间，和标签-如果他们有VIP卡，如果没有的话，是1。俱乐部开放时间是在08:00:00至21:00:00之间。假设没有两个客户同时到达。根据玩家的信息，有两个正整数:K(小于=100)-球桌的数量，M(小于K)-贵宾球桌的数量。最后一行包含M个贵宾球桌号。

9
20:52:00 10 0
08:00:00 20 0
08:02:00 30 0
20:51:00 10 0
08:10:00 5 0
08:12:00 10 1
20:50:00 10 0
08:01:30 15 1
20:53:00 10 1
3 1
2

输出

对于每个测试用例，首先打印到达时间、服务时间和等待时间，并以样例显示的格式为每一对参与者等待时间。然后在一行中打印出每个表所提供的播放器的数量。请注意，输出必须按照服务时间的时间顺序列出。等待时间必须被四舍五入到整数分钟(s)。如果在截止时间前不能得到一张表，他们的信息就不能被打印出来。

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:50:00 20:50:00 0
20:51:00 20:51:00 0
20:52:00 20:52:00 0
3 3 2

这个题目虽然没有什么算法上的技巧，但是对于一个事务的抽象能力的培养是十分重要的。

代码

[c++]

#include <iostream>
#include <algorithm>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <limits.h>
using namespace std;

struct players
{
    int arriveTime;
    int startServe;
    int serveTime;
    int waitTime;
    int isVIP;
};

//等待队列中的VIP客户
vector<players >vipPlayers;
//普通客户
vector<players >ordinaryPlayers;
//处理完输出信息的客户
vector<players >total;

struct tables
{
    int VIP;
    int cnt;
    int vacantTime;
};
tables t[101];


bool cmpPlayers(players a,players b)
{
    return a.arriveTime<b.arriveTime;
}

bool cmpStartServe(players a,players b)
{
    return a.startServe<b.startServe;
}

int main()
{
    int N,K,M,i=0;
    cin>>N;
    int hh,mm,ss,wait,vip;
    players temp;
    while(i<N)
    {
        scanf("%d:%d:%d %d %d",&hh,&mm,&ss,&wait,&vip);
        temp.arriveTime=hh*3600+mm*60+ss;
        temp.serveTime=wait*60;
        temp.isVIP=vip;
        i++;
        if(temp.arriveTime>=3600*21)continue;
        if(vip==1)vipPlayers.push_back(temp);
        else ordinaryPlayers.push_back(temp);
    }
    cin>>K>>M;
    for(int j=1;j<=K;j++)
    {
        t[j].VIP=0;
        t[j].vacantTime=8*3600;
        t[j].cnt=0;
    }
    int tag;
    for(int j=0;j<M;j++)
    {
        cin>>tag;
        t[tag].VIP=1;
    }

    if(ordinaryPlayers.size()>0)  sort(ordinaryPlayers.begin(),ordinaryPlayers.end(),cmpPlayers);//对到达时间排序 
    if(vipPlayers.size()>0)   sort(vipPlayers.begin(),vipPlayers.end(),cmpPlayers);//对到达时间排序 

    while(ordinaryPlayers.size()>0||vipPlayers.size()>0)//处理两个队列 
    {
        int minVacant=INT_MAX;
        int minVipVacant=INT_MAX;
        int index;
        int vipIndex;
        for(int j=1;j<=K;j++)
        {
            if(t[j].vacantTime<minVacant)//找到最小的空闲时间 
            {
                minVacant=t[j].vacantTime;
                index=j;
            }
            
            if(t[j].VIP==1&&t[j].vacantTime<minVipVacant) 
            {
                minVipVacant=t[j].vacantTime;
                vipIndex=j;
            }
        }
        
        if(t[index].vacantTime>=21*3600)break;
        
        players nextPlayers;
        
        if(vipPlayers.size()==0)
        {
            nextPlayers=ordinaryPlayers.front();
            ordinaryPlayers.erase(ordinaryPlayers.begin());
        }
        else if(ordinaryPlayers.size()==0)
        {
            nextPlayers=vipPlayers.front();
            vipPlayers.erase(vipPlayers.begin());
        }
        else
        {
            if(t[index].VIP==1)
            {
                if(vipPlayers.front().arriveTime<ordinaryPlayers.front().arriveTime||t[index].vacantTime>=vipPlayers.front().arriveTime)
                {
                    nextPlayers=vipPlayers.front();
                    vipPlayers.erase(vipPlayers.begin());
                }
                else
                {
                    nextPlayers=ordinaryPlayers.front();
                    ordinaryPlayers.erase(ordinaryPlayers.begin());
                }
            }
            else
            {
                if(vipPlayers.front().arriveTime<ordinaryPlayers.front().arriveTime)
                {
                    nextPlayers=vipPlayers.front();
                    vipPlayers.erase(vipPlayers.begin());
                }
                else
                {
                    nextPlayers=ordinaryPlayers.front();
                    ordinaryPlayers.erase(ordinaryPlayers.begin());
                }
            }
        }
        //控制每个人的时间在两小时之内,超过两小时按两个小时截断
        if(nextPlayers.serveTime>7200)nextPlayers.serveTime=7200;
        //这里需要记清楚：一旦有VIP桌子空闲，等待队列中的VIP客户就会选择VIP桌子，不管是否有普通桌子空闲
        if(nextPlayers.isVIP==1&&nextPlayers.arriveTime>=t[vipIndex].vacantTime)
        {
            nextPlayers.waitTime=0;
            nextPlayers.startServe=nextPlayers.arriveTime;
            t[vipIndex].vacantTime=nextPlayers.arriveTime+nextPlayers.serveTime;
            t[vipIndex].cnt++;
        }
        else
        {
            if(nextPlayers.arriveTime<=t[index].vacantTime)
            {
                nextPlayers.waitTime=t[index].vacantTime-nextPlayers.arriveTime;
                nextPlayers.startServe=t[index].vacantTime;
                t[index].vacantTime+=nextPlayers.serveTime;
            }
            else
            {
                nextPlayers.waitTime=0;
                nextPlayers.startServe=nextPlayers.arriveTime;
                t[index].vacantTime=nextPlayers.arriveTime+nextPlayers.serveTime;
            }
            t[index].cnt++;
        }
        total.push_back(nextPlayers);
    }
    
    
    sort(total.begin(),total.end(),cmpStartServe);
    for(int i=0;i<total.size();i++)
    {
        int waitMinutes=total[i].waitTime/60+(total[i].waitTime%60<30?0:1);
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",total[i].arriveTime/3600,
               (total[i].arriveTime%3600)/60,total[i].arriveTime%60,
               total[i].startServe/3600,(total[i].startServe%3600)/60,
               total[i].startServe%60,waitMinutes);
    }
    int first=1;
    for(int i=1;i<=K;i++)
    {
        if(first)first=0;
        else cout<<" ";
        cout<<t[i].cnt;
    }
    return 0;
}