说在前面
🎈今天给大家带来的是算法练习,题目为"餐厅【候桌问题】"。
问题描述
在小餐馆里，有几张双人餐桌，四人餐桌和六人餐桌。应将一个用餐者或两个用餐者安排在一个双人餐桌上，三个或四个用餐者应安排在一个四人餐桌上，五个或六个用餐者应安排一个六人餐桌 。
餐厅供应美味佳肴，很多人都喜欢在这里用餐。每天午餐时间到来，餐厅通常都是用餐者。如果没有合适的餐桌就餐，他们必须等到合适的餐桌。如果超过半小时，他们将前往另一家餐馆。
现在给出一天即将到来的用餐者名单，请计算有多少用餐者在此餐厅用餐。您可以假设每个用餐者坐下来离开餐厅需要半个小时。\
输入
有几个测试用例。每个案例的第一行包含由空格分隔的正整数，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--;
return n;
}
else{
//判断是否还有空桌
if(A > 0){
t_tail->p_next = node;
t_tail = node;
A--;
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;
}
t_tail->p_next = node;
t_tail = node;
t_head = t_head->p_next;
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--;
return n;
}
else{
if(A > 0){
t_tail->p_next = node;
t_tail = node;
A--;
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;
}
t_tail->p_next = node;
t_tail = node;
t_head = t_head->p_next;
return n;
}
return 0;
}
}
//四人桌用餐
else if(n <= 4){
if(f_head == NULL||f_tail == NULL){
f_head = node;
f_tail = node;
B--;
return n;
}
else{
if(B > 0){
f_tail->p_next = node;
f_tail = node;
B--;
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;
}
f_tail->p_next = node;
f_tail = node;
f_head = f_head->p_next;
return n;
}
return 0;
}
}
//六人桌用餐
else{
if(s_head == NULL||s_tail == NULL){
s_head = node;
s_tail = node;
C--;
return n;
}
else{
if(C > 0){
s_tail->p_next = node;
s_tail = node;
C--;
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;
}
s_tail->p_next = node;
s_tail = node;
s_head = s_head->p_next;
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;
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;
} ## 说在后面
🎉这里是 JYeontu，现在是一名前端工程师，有空会刷刷算法题，平时喜欢打打羽毛球🏸 ，平时也喜欢写些东西，既为自己记录📋，也希望可以对大家有那么一丢丢的帮助，写的不好望多多谅解🙇，写错的地方望指出，定会认真改进😊，在此谢谢大家的支持，我们下文再见🙌。
