Queueing at Bank【PAT 1017题】
题目链接：http://pat.zju.edu.cn/contests/pat-practise/1017
前面的1014题《Waiting in Line》也是银行柜台业务逻辑，只不过那道题窗口前维护着一个length>=1的队列，而这道题是窗口队列长度限制为1，那道题时间只精确到分，所以做的时候用了个minute++的时钟，而这道题时间精确到秒，所以用了个second++的秒表，其它的逻辑差不多。
这道题需要注意的地方比较多：
1.如果用户在早上08:00:00前来到银行，则需要在门外进行排队，且等待时间从此时开始算，而不是从08:00:00开始，比如A在07:59:59来到银行，则他的等待时间至少是1秒，如果他前面已经有人早早来到银行，那么他就要等更长的时间。
2.在17:00:01及以后到达银行的客户一律无效，而在此之前到达的客户一律有效
3.如果窗口此时有空闲，则检查客户队列，因为题目中的客户队列一次性给出，等于是预测了今天的银行进人情况，所以需要检查此时队列头的那个客户在当前时间下是否来到了一行，若没有来到银行，则窗口必须等待
备注：这道题我发现了printf("%.1lf\n", result);这句话有四舍五入的功能，比如result = 6.78，则会输出6.8。
1 //求等待时间的平均值,以秒算，最后再化成分
2 #include <stdio.h>
3 #include <stdlib.h>
4
5 typedef struct
6 {
7 int hour;
8 int minute;
9 int second;
10 int processtime;//<=60
11 int valid;//该客户算不算有效人头
12 long start;//记录客户进入银行的时间，以秒为单位，距离08:00的长度
13 long end;//开始得到服务的时间，end - start 即等待时间
14 }customer;
15
16 typedef struct
17 {
18 int haveCustomer;
19 int id;//该顾客在顾客队列中的编号
20 }windows;
21
22 customer *ct;
23 windows *wd;
24 int n, k;
25 int pos;//记录当前站在黄线外的第一个客户
26 long num;//有效客户数目
27 long sum;
28 double result;
29
30 int comp(const void *a, const void *b)
31 {
32 customer c = *(customer *)a;
33 customer d = *(customer *)b;
34 if(c.hour > d.hour) return 1;
35 else if(c.hour < d.hour) return -1;
36 else
37 {
38 if(c.minute > d.minute) return 1;
39 else if(c.minute < d.minute) return -1;
40 else
41 {
42 if(c.second > d.second) return 1;
43 else return -1;
44 }
45 }
46 }
47
48 long getStartTime(int hh, int mm, int ss)//计算该客户进入银行距离08:00的时长
49 {
50 long t;
51 t = 0;
52 if(hh < 8)//早上8点前到的,也要计算入等待时间内
53 {
54 t += (60 - ss);
55 t += (60 - (mm + 1)) * 60;
56 t += (8 - (hh + 1)) * 3600;
57 t = 0 - t;//时长记为负值，这样end-start的时候正好可以变成正值
58 return t;
59 }
60 else if((hh > 17) || (hh == 17 && (mm > 0 || ss > 0)))//下午17:00:01后到的
61 {
62 t = 50000;//最大有效值为32400(9*60*60)
63 return t;//这个客户不计算在num内
64 }
65 else
66 {
67 t += (hh - 8) * 3600;
68 t += mm * 60;
69 t += ss;
70 return t;
71 }
72
73 }
74
75 int windowsIsFull()
76 {
77 int i;
78 for(i = 0; i < k; i ++)
79 {
80 if(wd[i].haveCustomer == 0)
81 {
82 return 0;
83 }
84 }
85 return 1;
86 }
87
88 int findWindows()//找到最小编号的空窗口
89 {
90 int i;
91 for(i = 0; i < k; i ++)
92 {
93 if(wd[i].haveCustomer == 0)
94 {
95 return i;
96 }
97 }
98 }
99
100 int main()
101 {
102 int i;
103 long time;//秒表
104 int j;
105
106 while(scanf("%d %d", &n, &k) != EOF)
107 {
108 ct = (customer *)malloc(n * sizeof(customer));
109 for(i = 0; i < n; i ++)
110 {
111 scanf("%d:%d:%d %d", &ct[i].hour, &ct[i].minute, &ct[i].second, &ct[i].processtime);
112 ct[i].valid = 1;
113 if(ct[i].processtime > 60)
114 {
115 ct[i].processtime = 60;//不能占用窗口超过一个小时
116 }
117 }
118 wd = (windows *)malloc(k * sizeof(windows));
119 for(i = 0; i < k; i ++)
120 {
121 wd[i].haveCustomer = 0;
122 }
123 qsort(ct, n, sizeof(customer), comp);
124 for(i = 0; i < n; i ++)
125 {
126 ct[i].start = getStartTime(ct[i].hour, ct[i].minute, ct[i].second);
127 if(ct[i].start == 50000)
128 {
129 ct[i].valid = 0;
130 }
131 }//统一更新start，确定有效客户和无效客户分界线
132
133 pos = 0;
134 time = -1;//秒表
135 while(ct[pos].valid)//还有客户站在黄线外
136 {
137 while(!windowsIsFull())//先把窗口入满
138 {
139 if(!ct[pos].valid)//有效客户用完也没填满窗口
140 {
141 break;
142 }
143 if(time == -1)//如果pos是08:00:00以后到达的客户，此时窗口只能等待
144 {
145 if(ct[pos].start > 0)
146 {
147 break;
148 }
149 }
150 else
151 {
152 if(ct[pos].start > time)//客户现在还没有进入银行呢
153 {
154 break;
155 }
156 }
157 j = findWindows();
158 wd[j].haveCustomer = 1;//进入窗口
159 wd[j].id = pos;
160 if(time == -1)
161 {
162 ct[pos].end = 0;
163 }
164 else
165 {
166 ct[pos].end = time;
167 }
168 pos ++;
169 }
170 time ++;
171 for(i = 0; i < k; i ++)//轮询每个窗口
172 {
173 if(wd[i].haveCustomer == 1)//首先窗口得有客户
174 {
175 j = wd[i].id;
176 if(ct[j].end + (ct[j].processtime * 60) == time)//该客户此时处理完业务
177 {
178 wd[i].haveCustomer = 0;
179 }
180 }
181 }
182 }
183 sum = 0;
184 num = 0;
185 for(i = 0; i < n; i ++)
186 {
187 if(!ct[i].valid)
188 {
189 break;
190 }
191 else
192 {
193 //printf("%d:%d:%d进的人等待了:%ld\n",ct[i].hour, ct[i].minute, ct[i].second, ct[i].end - ct[i].start);
194 num ++;
195 sum += (ct[i].end - ct[i].start);
196 }
197 }
198 //printf("%ld %ld\n", num, sum);
199 result = ((double)sum) / 60;
200 result /= num;
201 printf("%.1lf\n", result);
202 }
203
204 return 0;
205 }
posted on 2012-03-20 19:35 Rafy 阅读(...) 评论(...) 编辑 收藏