队列模拟题——pat1026. Table Tennis

题意自己理解了，主要是两个队列维护，一个VIP队列，一个普通队列

搜集了一些坑（有些坑转自别的网站用于广大同学的测试之用）

普通人也有VIP的权益！！！屌丝逆袭有木有！！！

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
10 10
1 2 3 4 5 6 7 8 9 10

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

1.当有多个乒乓球台空闲时，vip顾客到了会使用最小id的vip球台，而不是最小id的球台，测试以下用例：

2

10:00:00 30 1

12:00:00 30 1

5 1

3

输出正确结果应为：

10:00:00 10:00:00 0

12:00:00 12:00:00 0

0 0 2 0 0

2.题目要求每对顾客玩的时间不超过2小时，那么当顾客要求玩的时间>2小时的时候，应该截断控制，测试以下用例：

2

18:00:00 180 1

20:00:00 60 1

1 1

1

输出的正确结果应为：

18:00:00 18:00:00 0

20:00:00 20:00:00 0

3.虽然题目中保证客户到达时间在08:00:00到21:00:00之间，但是根据最后的8个case来看，里面还是有不在这个时间区间内到达的顾客，所以建议还是稍加控制，测试以下用例：

1

21:00:00 80 1

1 1

1

输出的正确结果应为：

4.题目中说的round up to an integer minutes是严格的四舍五入，需要如下做：

wtime = (stime - atime + 30) / 60

而不是：

wtime = (stime - atime + 59) / 60

代码这次写的还是可以一看的，就贴上来吧

#include<stdio.h>

#include<queue>

#include<algorithm>

#include<iostream>

using namespace std;

struct VIPdata{//vip队列

    int starts;

    int startget;

    int lasts;

    int VIP;

    int id;

    friend bool operator <(VIPdata x,VIPdata y){

        if(x.VIP==y.VIP)

            return x.starts>y.starts;

        else

            return x.VIP<y.VIP;

    }

}s[];

struct Ordata{//普通队列

    int starts;

    int startget;

    int lasts;

    int VIP;

    int id;

    Ordata(int a,int b,int c,int d,int e){

        starts=a;startget=b;lasts=c;VIP=d;id=e;

    }

    friend bool operator <(Ordata x,Ordata y){

        return x.starts>y.starts;

    }

};

int ifplay[];//某人是否已经玩过

int cmp(VIPdata x,VIPdata y){

    return x.starts<y.starts;

}

struct Table{

    int ifuse;

    int end;

    int vip;

    int useNum;

}table[];

int main(){

    int n,tableNum,VipNum,PuNum;

    while(scanf("%d",&n)!=EOF){

        int i,hh,mm,ss,j;

        for(i=;i<=n;i++){

            ifplay[i]=;

            scanf("%d:%d:%d",&hh,&mm,&ss);

            s[i].starts=hh*+mm*+ss;

            scanf("%d",&mm);

            if(mm>)mm=;//不要超过2个小时

            s[i].lasts=mm*;

            scanf("%d",&s[i].VIP);

            s[i].id=i;

        }

        scanf("%d",&tableNum);

        scanf("%d",&VipNum);

        PuNum=tableNum-VipNum;

        for(i=;i<=tableNum;i++){

            table[i].ifuse=;

            table[i].end=;

            table[i].vip=;

            table[i].useNum=;

        }

        int temp;

        for(i=;i<=VipNum;i++){

            scanf("%d",&temp);

            table[temp].vip=;

        }

        sort(&s[],&s[+n],cmp);

        //for(i=1;i<=n;i++){

        //    printf("%02d:%02d:%02d %d\n",s[i].starts/3600,(s[i].starts%3600)/60,s[i].starts%60,s[i].VIP);

        //}

        int first=*,end=*;

        int Vipnow=,Punow=;

        priority_queue<Ordata>Orqq;

        priority_queue<VIPdata>VIPqq;

        j=;

        int k,x;

        for(i=first;i<end;i++){

            for(k=;k<=tableNum;k++){//退台球桌

                if(table[k].ifuse==)continue;

                if(table[k].end==i){

                    table[k].ifuse=;

                    if(table[k].vip==)Vipnow--;

                    else Punow--;

                    table[k].ifuse=;

                }

            }

            //到点的人排队

            while(s[j].starts==i&&j<=n){

                Orqq.push(Ordata(s[j].starts,s[j].startget,s[j].lasts,s[j].VIP,s[j].id));

                VIPqq.push(s[j]);j++;

            }

            if((Vipnow+Punow)==tableNum)continue;

            for(k=Vipnow+;k<=VipNum;k++){//排队中的人进台球桌 有VIP桌先满足VIP

                if(VIPqq.empty())break;

                if(VIPqq.top().VIP==)break;

                while(!VIPqq.empty()&&ifplay[VIPqq.top().id]==/*||(VIPqq.top().lasts+i)>end)*/){

                    VIPqq.pop();

                }if(VIPqq.empty())break;

                int rx=-;

                for(x=;x<=tableNum;x++){

                    if(table[x].ifuse==)continue;

                    if(table[x].vip==)continue;

                    rx=x;break;

                }if(rx==-)break;

                printf("%02d:%02d:%02d",(VIPqq.top().starts/),(VIPqq.top().starts%)/,VIPqq.top().starts%);

                printf(" %02d:%02d:%02d",(i/),(i%)/,i%);

                printf(" %d\n",(i-VIPqq.top().starts+)/);//这里注意+30

                table[rx].end=VIPqq.top().lasts+i;

                table[rx].ifuse=;

                table[rx].useNum++;

                Vipnow++;

                ifplay[VIPqq.top().id]=;

                VIPqq.pop();

            }

            //排队中的人进台球桌 现在按普通队列排

            if((Vipnow+Punow)==tableNum)continue;

            for(k=;k<=tableNum;k++){//普通人也可以玩VIP桌子

                if(Orqq.empty())break;

                while(!Orqq.empty()&&ifplay[Orqq.top().id]==){

                    Orqq.pop();

                }if(Orqq.empty())break;

                int rx=-;

                for(x=;x<=tableNum;x++){

                    if(table[x].ifuse==)continue;

                    rx=x;break;

                }if(rx==-)break;

                printf("%02d:%02d:%02d",(Orqq.top().starts/),(Orqq.top().starts%)/,Orqq.top().starts%);

                printf(" %02d:%02d:%02d",(i/),(i%)/,i%);

                printf(" %d\n",(i-Orqq.top().starts+)/);//这里注意+30

                table[rx].end=Orqq.top().lasts+i;

                table[rx].ifuse=;

                table[rx].useNum++;

                if(table[rx].vip==)Vipnow++;

                else

                    Punow++;

                ifplay[Orqq.top().id]=;

                Orqq.pop();

            }

        }

        int ok=;

        for(i=;i<=tableNum;i++){

            if(ok==)ok=;

            else printf(" ");

            printf("%d",table[i].useNum);

        }printf("\n");

    }

    return ;

}

巴特西

队列模拟题——pat1026. Table Tennis

最新文章

热门文章