【PAT甲级】1026 Table Tennis (30 分)(结构体排序,trick较多)

题意:

输入一个正整数N(<=10000),表示客户(对)的大小,接着输入N行数据,每行包括一对顾客到场的时间,想要玩的时间,以及是否是VIP客户。接下来输入两个正整数K,M(K<=100,M<=K),表示球桌的数量和其中VIP球桌的数量,接下来输入一行M个正整数,表示VIP球桌的编号。依照每对客户开始打球的时间由小到大顺序输出N行:他们的到场时间和开始打球的时间以及四舍五入输入等待时长,最后一行输出每张球桌服务的客户对数。如果客户21点前没有得到服务,则不输出他们的数据。

trick:

第8组数据包含需要对分钟进行四舍五入的数据,一开始没用翻译采取直接上取整发现这个点过不去。

第3组数据包含恰好21点到达的客户,他们是不可以接受服务的,这个点找了较长时间才发现。

第7组数据包含VIP客户需要先安排到VIP球桌的数据且VIP球桌不空闲的数据。

第5组数据包含VIP客户需要安排到VIP球桌且VIP球桌空闲的数据。

第1,2组数据包含当前无球桌空闲的数据。

第4,6组数据包含当前无VIP客户的数据。

第0组数据即为样例。

(对于数据的揣测基于我提交代码的不同,可能有误,仅希望有缘人可以借此少走弯路)

对于题干最后一句话:

On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.

On the other hand在Codeforces网站上的常用意为换句话说,意思是On the other hand后面的话和上一句话表达的意思是一样的只是换了种说法,这道题中On the other hand的意思应该是另一方面,因为我经常打Codeforces所以刚做题时我习惯地忽略了On the other hand后面的话,这道题的题意确实使这道题蒙上了一些细节方面的理解薄雾。

AAAAAccepted code:

  1 #define HAVE_STRUCT_TIMESPEC
  2 #include<bits/stdc++.h>
  3 using namespace std;
  4 int table[107];
  5 int tt[107];
  6 int tans[107];
  7 int vipid[10007];
  8 typedef struct customers{
  9     string s;
 10     int t,pt,ft,flg;
 11 };
 12 customers c[10007];
 13 typedef struct ans{
 14     string s;
 15     int t,st;
 16 };
 17 ans a[10007];
 18 bool cmp(customers a,customers b){
 19     return a.t<b.t;
 20 }
 21 bool cmp2(ans a,ans b){
 22     return a.st<b.st;
 23 }
 24 char anss[10007][17];
 25 int main(){
 26     int n;
 27     cin>>n;
 28     for(int i=1;i<=n;++i){
 29         cin>>c[i].s>>c[i].pt>>c[i].flg;
 30         if(c[i].pt>=120)
 31             c[i].pt=120;
 32         c[i].pt*=60;
 33         c[i].t=(c[i].s[0]-'0')*36000+(c[i].s[1]-'0')*3600+(c[i].s[3]-'0')*600+(c[i].s[4]-'0')*60+(c[i].s[6]-'0')*10+c[i].s[7]-'0';
 34     }
 35     int sum,vip;
 36     cin>>sum>>vip;
 37     int x;
 38     for(int i=1;i<=vip;++i){
 39         cin>>x;
 40         table[x]=1;
 41     }
 42     sort(c+1,c+1+n,cmp);
 43     int cnt=0;
 44     for(int i=1;i<=n;++i)
 45         if(c[i].flg)
 46             vipid[++cnt]=i;
 47     int sew=0,mn=1e9,pos=0;
 48     int cntt=1;
 49     for(int i=1;i<=n;++i){
 50         if(a[i].t)
 51             continue;
 52         if(c[i].t>=21*3600)
 53             break;
 54         sew=0,mn=1e9,pos=0;
 55         if(c[i].flg==1){
 56             for(int j=1;j<=sum;++j){
 57                 if(!table[j])
 58                     continue;
 59                 if(tt[j]<=c[i].t){
 60                     tt[j]=c[i].t+c[i].pt;
 61                     a[i].s=c[i].s;
 62                     a[i].t=c[i].t;
 63                     a[i].st=c[i].t;
 64                     ++tans[j];
 65                     sew=1;
 66                     break;
 67                 }
 68                 if(tt[j]<mn){
 69                     mn=tt[j];
 70                     pos=j;
 71                 }
 72             }
 73             if(sew)
 74                 continue;
 75             for(int j=1;j<=sum;++j){
 76                 if(tt[j]<=c[i].t){
 77                     tt[j]=c[i].t+c[i].pt;
 78                     a[i].s=c[i].s;
 79                     a[i].t=c[i].t;
 80                     a[i].st=c[i].t;
 81                     ++tans[j];
 82                     sew=1;
 83                     break;
 84                 }
 85                 if(tt[j]<mn){
 86                     mn=tt[j];
 87                     pos=j;
 88                 }
 89             }
 90             if(sew)
 91                 continue;
 92             if(tt[pos]<21*3600){
 93                 a[i].st=tt[pos];
 94                 tt[pos]+=c[i].pt;
 95                 a[i].s=c[i].s;
 96                 a[i].t=c[i].t;
 97                 ++tans[pos];
 98             }
 99             continue;
100         }
101         sew=0,mn=1e9,pos=0;
102         for(int j=1;j<=sum;++j){
103             if(tt[j]<=c[i].t){
104                 tt[j]=c[i].t+c[i].pt;
105                 a[i].s=c[i].s;
106                 a[i].t=c[i].t;
107                 a[i].st=c[i].t;
108                 ++tans[j];
109                 sew=1;
110                 break;
111             }
112             if(tt[j]<mn){
113                 mn=tt[j];
114                 pos=j;
115             }
116         }
117         if(sew)
118             continue;
119         if(table[pos]&&tt[pos]<21*3600){
120             while(a[vipid[cntt]].t)
121                 ++cntt;
122             if(cntt<=cnt&&c[vipid[cntt]].t<=tt[pos]){
123                 a[vipid[cntt]].st=tt[pos];
124                 tt[pos]+=c[vipid[cntt]].pt;
125                 a[vipid[cntt]].s=c[vipid[cntt]].s;
126                 a[vipid[cntt]].t=c[vipid[cntt]].t;
127                 --i;
128                 ++tans[pos];
129                 ++cntt;
130             }
131             else{
132                 a[i].st=tt[pos];
133                 tt[pos]+=c[i].pt;
134                 a[i].s=c[i].s;
135                 a[i].t=c[i].t;
136                 ++tans[pos];
137             }
138         }
139         else if(tt[pos]<21*3600){
140             a[i].st=tt[pos];
141             tt[pos]+=c[i].pt;
142             a[i].s=c[i].s;
143             a[i].t=c[i].t;
144             ++tans[pos];
145         }
146     }
147     sort(a+1,a+1+n,cmp2);
148     for(int i=1;i<=n;++i){
149         if(!a[i].t)
150             continue;
151         cout<<a[i].s<<" ";
152         int temp=a[i].st;
153         anss[i][0]=a[i].st/36000+'0';
154         a[i].st%=36000;
155         anss[i][1]=a[i].st/3600+'0';
156         a[i].st%=3600;
157         anss[i][2]=':';
158         anss[i][3]=a[i].st/600+'0';
159         a[i].st%=600;
160         anss[i][4]=a[i].st/60+'0';
161         a[i].st%=60;
162         anss[i][5]=':';
163         anss[i][6]=a[i].st/10+'0';
164         a[i].st%=10;
165         anss[i][7]=a[i].st+'0';
166         cout<<anss[i]<<" ";
167         int x=(temp-a[i].t)/60;
168         if((temp-a[i].t)%60>=30)
169             ++x;
170         cout<<x<<"
";
171     }
172     for(int i=1;i<=sum;++i)
173         cout<<tans[i]<<((i==sum)?"":" ");
174     return 0;
175 }
保持热爱 不懈努力 不试试看怎么知道会失败呢(划掉) 世上无难事 只要肯放弃(划掉)
原文地址:https://www.cnblogs.com/ldudxy/p/11479073.html