餐厅
描述
在小餐馆里，有几张双人餐桌，四人餐桌和六人餐桌。应将一个用餐者或两个用餐者安排在一个双人餐桌上，三个或四个用餐者应安排在一个四人餐桌上，五个或六个用餐者应安排一个六人餐桌 。
餐厅供应美味佳肴，很多人都喜欢在这里用餐。每天午餐时间到来，餐厅通常都是用餐者。如果没有合适的餐桌就餐，他们必须等到合适的餐桌。如果超过半小时，他们将前往另一家餐馆。
现在给出一天即将到来的用餐者名单，请计算有多少用餐者在此餐厅用餐。您可以假设每个用餐者坐下来离开餐厅需要半个小时。
输入
有几个测试用例。每个案例的第一行包含由空格分隔的正整数，A，B和C（A，B，C> 0，A + B + C <= 100），它们是双座位餐桌的数量，四个座位的餐桌和六个座位的餐桌数量。从第二行开始，表示到来的一组用餐者，每行包含两个整数，T和N（0 <N <= 6），表示该组用餐者的到达时间和数量。到达时间Ť由HH：MM表示，并且在08:00和22:00之间固定（餐厅在23:00关闭）列表按每个组的到达时间按升序排序，您可以假设没有组同时到达。每个测试用例以“#”行结束。
A = B = C = 0的测试用例结束输入。
输出
对于每个测试用例，您应该输出一个整数，即在餐厅以分开的线路吃食物的食客总数。
输入样例 1
1 1 1
10:40 1
10:50 2
11:00 4
#
1 1 1
10:40 1
10:50 2
11:00 2
#
1 2 1
10:30 1
10:40 3
10:50 2
11:00 1
11:20 5
#
0 0 0
输出样例 1
7
3
12
读完题目后，我们不难看出，这道题目我们可以用队列来解题，这里我用链表来模拟队列。
按照我们平时吃饭的经验，我们可以知道进餐馆后主要有以下几种情况：
1、餐馆里都是空桌，我们可以直接上桌点菜
2、餐馆里有人，都还有空桌，我们也可以直接上桌点菜
3、餐馆里暂时没有空余的位置，所以我们需要等，我们会等最快吃完的那一桌吃完，而这里又分两种情况
（1）我们又足够的时间等最快的那一桌吃完，所以我们等
（2）我们觉得要等太久，所以就不等了
下面我们结合题目给出的样例分析一下：
（1）
1 1 1
10:40 1
10:50 2
11:00 4
#
这里双人桌、四人桌、六人桌各有一张
这一例子的流程如上图，所有人都可以吃上饭，我们只需要把上了桌的客人的人数全部加上（即右边的数字），便可得出结果为7。接下来让我们再看看另一种情况：
（2）
1 1 1
10:40 1
10:50 2
11:00 2
还是双人桌、四人桌、六人桌各有一张
从上图可以看出第二批客人和第三批客人都需要等待，当第一批客人吃完的时候，第二批客人还在等，所以第二批就可以直接上桌了，而第三批客人则还需要等第二批的客人吃完，最后等了半个小时第二批客人还没有吃完，所以第三批客人就走了。所以可以吃上饭的只有前面两批客人，此时我们讲右边的数据加起来就是答案了。
经过分析，我们知道我们主要要解决以下问题：
■如何判断客人来的时候需要等多久才能吃上饭，这里我用了一个函数来判断，代码如下：
int judg(int hh,int mm,int h,int m){ //h:m为当前餐馆里最早来的那批客人的上桌时间 //计算第一批客人离开时间 m +=30; if(m >= 60){ h++; m %= 60; } //离开时间早于来客时间 ，来客直接上桌 if(hh > h || (hh == h && mm >= m)) return 1; //离开时间晚于来客时间，来客等待 mm += 30; if(mm >= 60){ hh++; mm %= 60; } //可以等到 if(hh > h || (hh == h && mm >= m)) return 2; //等不到 return 0; }
■如何表示各种桌子的使用情况
（1）//定义桌子结构体
struct desk{ int HH; int MM; struct desk* p_next; };
（2）//定义双人桌的头和尾
struct desk* t_head = NULL; struct desk* t_tail = NULL;
（3）记录双人桌的用餐情况
//双人桌用餐 if(n <= 2){ if(t_head == NULL||t_tail == NULL){ t_head = node; t_tail = node; A--; // printf("HH = %d MM = %d 只有我ttt\n",node->HH,node->MM); return n; } else{ //判断是否还有空桌 if(A > 0){ t_tail->p_next = node; t_tail = node; A--; // printf("HH = %d MM = %d 上桌ttt\n",node->HH,node->MM); return n; } if(judg(HH,MM,t_head->HH,t_head->MM) >= 1){ if(judg(HH,MM,t_head->HH,t_head->MM) == 2){ int h = t_head->HH; int m = t_head->MM; m += 30; if(m>=60){ h++; m%=60; } node->HH = h; node->MM = m; // printf("ttt等……h = %d m = %d\n",h,m); } t_tail->p_next = node; t_tail = node; t_head = t_head->p_next; // printf("HH = %d MM = %d 换桌ttt\n",node->HH,node->MM); return n; } return 0; } }
另外四人桌和六人桌我也用了同样的方法，就不一一说明了。
AC代码如下：
#include<stdio.h> #include<malloc.h> #include<string.h> #include <stdlib.h> int A,B,C; //定义桌子结构体 struct desk{ int HH; int MM; struct desk* p_next; }; //两人桌 struct desk* t_head = NULL; struct desk* t_tail = NULL; //四人桌 struct desk* f_head = NULL; struct desk* f_tail = NULL; //六人桌 struct desk* s_head = NULL; struct desk* s_tail = NULL; int judg(int hh,int mm,int h,int m){ //计算第一批客人离开时间 m +=30; if(m >= 60){ h++; m %= 60; } //离开时间早于来客时间 ，来客直接上桌 if(hh > h || (hh == h && mm >= m)) return 1; //离开时间晚于来客时间，来客等待 mm += 30; if(mm >= 60){ hh++; mm %= 60; } //可以等到 if(hh > h || (hh == h && mm >= m)) return 2; //等不到 return 0; } //创建链表(客人用餐) int addNode(int n,int HH,int MM){ struct desk* node = (struct desk*)malloc(sizeof(struct desk)); node->HH = HH; node->MM = MM; node->p_next = NULL; //双人桌用餐 if(n <= 2){ if(t_head == NULL||t_tail == NULL){ t_head = node; t_tail = node; A--; // printf("HH = %d MM = %d 只有我ttt\n",node->HH,node->MM); return n; } else{ if(A > 0){ t_tail->p_next = node; t_tail = node; A--; // printf("HH = %d MM = %d 上桌ttt\n",node->HH,node->MM); return n; } if(judg(HH,MM,t_head->HH,t_head->MM) >= 1){ if(judg(HH,MM,t_head->HH,t_head->MM) == 2){ int h = t_head->HH; int m = t_head->MM; m += 30; if(m>=60){ h++; m%=60; } node->HH = h; node->MM = m; // printf("ttt等……h = %d m = %d\n",h,m); } t_tail->p_next = node; t_tail = node; t_head = t_head->p_next; // printf("HH = %d MM = %d 换桌ttt\n",node->HH,node->MM); return n; } return 0; } } //四人桌用餐 else if(n <= 4){ if(f_head == NULL||f_tail == NULL){ f_head = node; f_tail = node; B--; // printf("HH = %d MM = %d 只有我fff\n",node->HH,node->MM); return n; } else{ if(B > 0){ f_tail->p_next = node; f_tail = node; B--; // printf("HH = %d MM = %d 上桌fff\n",node->HH,node->MM); return n; } if(judg(HH,MM,f_head->HH,f_head->MM) >= 1){ if(judg(HH,MM,f_head->HH,f_head->MM) == 2){ int h = f_head->HH; int m = f_head->MM; m += 30; if(m>=60){ h++; m%=60; } node->HH = h; node->MM = m; // printf("等fff……h = %d m = %d\n",h,m); } f_tail->p_next = node; f_tail = node; f_head = f_head->p_next; // printf("HH = %d MM = %d 换桌fff\n",node->HH,node->MM); return n; } return 0; } } //六人桌用餐 else{ if(s_head == NULL||s_tail == NULL){ s_head = node; s_tail = node; C--; // printf("HH = %d MM = %d 只有我ssss\n",node->HH,node->MM); return n; } else{ if(C > 0){ s_tail->p_next = node; s_tail = node; C--; // printf("HH = %d MM = %d 上桌sss\n",node->HH,node->MM); return n; } if(judg(HH,MM,s_head->HH,s_head->MM) >= 1){ if(judg(HH,MM,s_head->HH,s_head->MM) == 2){ int h = s_head->HH; int m = s_head->MM; m += 30; if(m>=60){ h++; m%=60; } node->HH = h; node->MM = m; // printf("等sss……h = %d m = %d\n",h,m); } s_tail->p_next = node; s_tail = node; s_head = s_head->p_next; // printf("HH = %d MM = %d 换桌sss\n",node->HH,node->MM); return n; } return 0; } } return 0; } int main() { while(1){ scanf("%d %d %d",&A,&B,&C); if((A == 0) && (B == 0) && (C == 0)) break; int sum = 0; int HH=0,MM=0,N=0,i=0; while(scanf("%d:%d %d",&HH,&MM,&N)!=EOF){ char ch=getchar(); if(ch=='#') break; // printf("HH=%d MM=%d N=%d\n",HH,MM,N); sum += addNode(N,HH,MM); } printf("%d\n",sum); sum = 0; //双人桌 t_head = NULL; t_tail = NULL; //四人桌 f_head = NULL; f_tail = NULL; //六人桌 s_head = NULL; s_tail = NULL; } return 0; }
