Home PAT 1026 Table Tennis
Post
Cancel

PAT 1026 Table Tennis

Link

这题真把我写吐了 🤮 调试了一下午之后终于 AC …

题意高深莫测, 全靠测试点来猜.

注意: 没有“要给普通客户优先分配普通桌子”的意思! 只有“要给 VIP 客户优先分配 VIP 桌子”的说法.

再就是: 球员打球时间超过两小时的,都按照两小时计算, 否则测试点 4 过不了.

别忘了输入的 play time 是以分钟为单位的, 而对于 hh:mm:ss 格式的到达时间我们通常转换成秒来计算, 所以后来加的时候 play 别忘了乘以 60.

我的解题思路是这样的:

while(…){

  • 如果当前有空闲桌子 index (注意,按照编号从小到大寻找,遇到第一个空闲的就停下来):
    • if 当前客户是 VIP 客户 && 桌子 index 不是 VIP 桌子:
      • 看看有没有已经空闲的 VIP 桌子 (因为要优先给 VIP 客户用 VIP 桌子):
        • 如果有, 就分配编号最小的那个 VIP 桌子给当前客户, continue.
    • else if 当前客户是普通客户 && 桌子 index 是 VIP 桌子:
      • 看看等待队列中有没有 VIP 客户 (因为他们可以插队, 但仅限于插队使用 VIP 桌子):
        • 如果有, 就让编号最小的那个 VIP 客户插队使用当前桌子, continue. (这里注意, 下一个遍历到的客户还是当前这个普通客户)
    • 直接将桌子 index 分配给当前客户
  • 如果当前没有空闲桌子, 就找到最快能够空闲的桌子 index:
    • if 当前客户是 VIP 客户 && 桌子 index 不是 VIP 桌子:
      • 看看有没有将要和 index 同时空闲的 VIP 桌子 (因为要优先给 VIP 客户用 VIP 桌子):
        • 如果有, 就分配编号最小的那个 VIP 桌子给当前客户, continue.
    • else if 当前客户是普通客户 && 桌子 index 是 VIP 桌子:
      • 看看等待队列中有没有 VIP 客户 (因为他们可以插队, 但仅限于插队使用 VIP 桌子):
        • 如果有, 就让编号最小的那个 VIP 客户插队使用当前桌子, continue. (这里注意, 下一个遍历到的客户还是当前这个普通客户)
    • 直接将桌子 index 分配给当前客户

}

最后再按照 serve time 排序, 就可以输出了.

AC 代码如下 (注释很详细):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <cmath>
using namespace std;
const int STARTTIME=8*3600,ENDTIME=21*3600;
int n,k,m;
struct node{
    int time,play,tag,serve=ENDTIME;
};
bool cmp1(const node &a,const node&b){
    return a.time<b.time;
}
bool cmp2(const node &a,const node&b){
    if(a.serve!=b.serve) return a.serve<b.serve;
    return a.time>b.time;//这里的排序题目中没有明说,应该也没有相关测试点,但是如果在牛客上提交就要这样判断,否则测试点10过不了(牛客有10个测试点)
}
vector<node>player;
int tableCount[110],tableTime[110];
bool vip[110],served[10010];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int hh,mm,ss,time,play,tag;
        scanf("%d:%d:%d %d %d",&hh,&mm,&ss,&play,&tag);
        play=min(play,120);
        time=hh*3600+mm*60+ss;
        if(time<ENDTIME){
            node tmp;
            tmp.time=time,tmp.play=play*60,tmp.tag=tag;
            player.push_back(tmp);
        }
    }
    sort(player.begin(),player.end(),cmp1);
    scanf("%d%d",&k,&m);
    for(int i=1;i<=m;++i){
        int vipid;
        scanf("%d",&vipid);
        vip[vipid]=true;
    }
    for(int i=1;i<=k;++i) tableTime[i]=STARTTIME;
    int p=0;
    while(p<player.size()){
        if(served[p]){p++;continue;}
        //并不是去找最小的tableTime,而是找第一个空闲的;如果都不空闲才是找最小的tableTime
        int index=0,cur=ENDTIME;
        for(int t=1;t<=k;++t){
            if(tableTime[t]<=player[p].time){
                cur=tableTime[t];
                index=t;
                break;
            }
            if(tableTime[t]<cur){
                cur=tableTime[t];
                index=t;
            }
        }
        if(index==0||cur>=ENDTIME) break;
        if(tableTime[index]>player[p].time){//当前没有空闲桌子
            if(player[p].tag&&!vip[index]){//当前客户是VIP,但是index桌子不是VIP桌子
                //找有没有和index同时空闲的编号最小的VIP桌子
                bool flag=false;
                for(int t=1;t<=k;++t)
                    if(vip[t]&&tableTime[t]==tableTime[index]){
                        flag=true;
                        player[p].serve=tableTime[t];
                        tableTime[t]=player[p].serve+player[p].play;
                        tableCount[t]++;
                        p++;
                        break;
                    }
                if(flag) continue;
            }else if(!player[p].tag&&vip[index]){//当前不是VIP客户但是是VIP桌子
                //寻找队列中的第一个VIP客户,让VIP客户插队
                bool flag=false;
                for(int i=p+1;i<player.size();++i){
                    if(served[i]) continue;
                    if(player[i].time>tableTime[index]) break;
                    if(player[i].tag){//有在等的VIP,VIP插队
                        flag=true;
                        served[i]=true;
                        player[i].serve=tableTime[index];
                        tableTime[index]=player[i].serve+player[i].play;
                        tableCount[index]++;
                        break;
                    }
                }
                if(flag) continue;
            }
            //剩下的两种情况就是:是VIP客户且index是VIP桌子、是普通客户且index是普通桌子
            //那就直接分配
            player[p].serve=tableTime[index];
            tableTime[index]=player[p].serve+player[p].play;
            tableCount[index]++;
            p++;
        }else{//当前有空闲桌子
            if(player[p].tag&&!vip[index]){//当前客户是VIP,但是index桌子不是VIP桌子
                //找有没有已经空闲的编号最小的VIP桌子
                bool flag=false;
                for(int t=1;t<=k;++t)
                    if(vip[t]&&tableTime[t]<=player[p].time){
                        flag=true;
                        player[p].serve=player[p].time;
                        tableTime[t]=player[p].serve+player[p].play;
                        tableCount[t]++;
                        p++;
                        break;
                    }
                if(flag) continue;
            }else if(!player[p].tag&&vip[index]){//当前不是VIP客户但是是VIP桌子
                //寻找队列中的第一个VIP客户,让VIP客户插队
                bool flag=false;
                for(int i=p+1;i<player.size();++i){
                    if(served[i]) continue;
                    if(player[i].time>tableTime[index]) break;
                    if(player[i].tag){//有在等的VIP,VIP插队
                        flag=true;
                        served[i]=true;
                        player[i].serve=player[i].time;
                        tableTime[index]=player[i].serve+player[i].play;
                        tableCount[index]++;
                        break;
                    }
                }
                if(flag) continue;
            }
            //剩下的两种情况就是:是VIP客户且index是VIP桌子、是普通客户且index是普通桌子
            //那就直接分配
            player[p].serve=player[p].time;
            tableTime[index]=player[p].serve+player[p].play;
            tableCount[index]++;
            p++;
        }
    }
    sort(player.begin(),player.end(),cmp2);
    for(int i=0;i<player.size();++i){
        if(player[i].serve>=ENDTIME) break;
        int hh=player[i].time/3600,mm=(player[i].time/60)%60,ss=player[i].time%60;
        int shh=player[i].serve/3600,smm=(player[i].serve/60)%60,sss=player[i].serve%60;
        int wait=round((player[i].serve-player[i].time)*1.0/60);
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",hh,mm,ss,shh,smm,sss,wait);
    }
    for(int i=1;i<=k;++i){
        if(i!=1) printf(" ");
        printf("%d",tableCount[i]);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.