看前须知

要点介绍和简要声明.

第四次上机题汇总

栈操作（栈-基本题）.

C程序括号匹配检查.

计算器(后缀表达式实现)（只要打出优先级表==有手就行）.

BUAA(2021春)文本编辑操作模拟（简）a——介绍两种方法.

BUAA(2021春)银行排队模拟（生产者-消费者模拟）——理解题意有点小难.

题目内容

问题描述

一个系统模仿另一个系统行为的技术称为模拟，如飞行模拟器。模拟可以用来进行方案论证、人员培训和改进服务。计算机技术常用于模拟系统中。

**生产者-消费者（Server-Custom）**是常见的应用模式，见于银行、食堂、打印机、医院、超等提供服务和使用服务的应用中。这类应用的主要问题是消费者如果等待（排队）时间过长，会引发用户抱怨，影响服务质量；如果提供服务者（服务窗口）过多，将提高运管商成本。（经济学中排队论）

假设某银行网点有五个服务窗口，分别为三个对私、一个对公和一个外币窗口。银行服务的原则是先来先服务。通常对私业务人很多，其它窗口人则较少，可临时改为对私服务。假设当对私窗口等待服务的客户（按实际服务窗口）平均排队人数超过（大于或等于）7人时，等待客户将可能有抱怨，影响服务质量，此时银行可临时将其它窗口中一个或两个改为对私服务，当客户少于7人时，将立即恢复原有业务。设计一个程序用来模拟银行服务。

说明：

1. 增加服务窗口将会增加成本或影响其它业务，因此，以成本增加或影响最小为原则来增加服务窗口，即如果增加一个窗口就能使得按窗口平均等待服务人数小于7人，则只增加一个窗口。一旦按窗口平均等待服务人数小于7人，就减少一个所增加的窗口。

2. 为了简化问题，假设新到客户是在每个服务周期开始时到达。

3. 当等待服务人数发生变化时（新客户到达或有客户已接受服务），则及时计算按实际服务窗口平均等待服务人数，并按相应策略调整服务窗口数（增加或减少额外的服务窗口，但对私窗口不能减少）。注意：只在获取新客户（不管到达新客户数是否为0）时或已有客户去接受服务时，才按策略调整服务窗口数。进一步讲，增加服务窗口只在有客户到达的周期内进行（也就是说增加窗口是基于客户的感受，银行对增加窗口是不情愿的，因为要增加成本，一旦不再有新客户来，银行是不会再增加服务窗口的）；一旦有客户去接受服务（即等待客户减少），银行将根据策略及时减少服务窗口，因此，在每个周期内，有客户去接受服务后要马上判断是否减少服务窗口（因为能减少成本，银行是积极的）

本问题中假设对公和对外币服务窗口在改为对私服务时及服务期间没有相应因公或外币服务新客户到达（即正好空闲），同时要求以增加成本或影响最小为前提，来尽最大可能减少对私服务客户等待时间。

输入形式

首先输入一个整数表示时间周期数，然后再依次输入每个时间周期中因私业务的客户数。注：一个时间周期指的是银行处理一笔业务的平均处理时间，可以是一分钟、三分钟或其它。例如：

6

2 5 13 11 15 9

说明：表明在6个时间周期内，第1个周期来了2个（序号分别为1,2），第2个来了5人（序号分别为3,4,5,6,7），以此类推。

输出形式

每个客户等待服务的时间周期数。输出形式如下：

用户序号 : 等待周期数

说明：客户序号与等待周期数之间用符号:分隔，冒号（:）两边各有一个空格，等待周期数后直接为回车。

样例

【样例输入】

4

2  5  13  11

 

【样例输出】

1 : 0

2 : 0

3 : 0

4 : 0

5 : 0

6 : 1

7 : 1

8 : 0

9 : 1

10 : 1

11 : 1

12 : 1

13 : 2

14 : 2

15 : 2

16 : 3

17 : 3

18 : 3

19 : 4

20 : 4

21 : 3

22 : 4

23 : 4

24 : 4

25 : 5

26 : 5

27 : 5

28 : 6

29 : 6

30 : 6

31 : 7

样例说明

样例输入表明有四个时间周期，第一个周期来了2人（序号1-2）；第二个周期来了5人（序号3-7）；第三个周期来了13人（序号8-20）；第四个周期来了11人（序号21-31）。由于第一个时间周期内只来了2人，银行（有三个服务窗口）能及时提供服务，因此客户等待时间为0；第二个时间周期内来了5人，银行一个周期内一次只能服务3人，另有2个在下个周期内服务，因此等待时间为1，其它类推。

题解

易错点和难点

本题最大难度在于怎么理解题意，这里笔者点播一下

1. 增加的条件是“本周期有新客户（即使为0）”，即若输入是4，在第4周期后便不会再有增加柜台的操作，只有减少。

2. 注意理解题中一旦按窗口平均等待服务人数小于7人，就减少一个所增加的窗口的含义，并非要求始终保持窗口平等待人数小于7人

3. 队列人数增加->判断是否应该增加窗口
   队列人数减少->判断是否应该减少窗口
   题目并未要求每次服务过程中平均等待人数均少于7人。

4. 其实就是有人来的周期和没有人来的周期内，判断窗口开放的数量不一样（银行的消极和积极状态不同）

参考代码

#include<stdio.h>
struct queue{
	int time[3000];
};
struct queue q;
int head=1,tail=1;
int n,m,op,i;
int min(int x,int y)
{
	return x>y?y:x;
}
void chooseOP1(int n)
{
	if(n<21)	op=3;    //开放窗口个数 
	else if(n>=21 && n<28)		op=4;
	else op=5;
}
void chooseOP2(int n)
{
	if(n<28)	op=3;    //开放窗口个数 
	else if(n>=28 && n<35)		op=4;
	else op=5;
}
int main()
{	
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		tail+=m;    //队尾增加 
		chooseOP1(tail-head);	
		for(i=head;i<min(head+op,tail);i++)
		{
			printf("%d : %d\n",i,q.time[i]);   //输出已经在窗口的客户
		}
		for(i=head+op;i<tail;i++)
		{
			q.time[i]++;              //等待的客户周期加1 
		}	
		head=min(head+op,tail);       //出队 
		chooseOP1(tail-head);
	}
	while(head<tail)
	{
		chooseOP2(tail-head);
		for(i=head;i<min(head+op,tail);i++)
		{
			printf("%d : %d\n",i,q.time[i]);   //输出已经在窗口的客户
		}
		for(i=head+op;i<tail;i++)
		{
			q.time[i]++;              //等待的客户周期加1 
		}	
		head=min(head+op,tail);       //出队 
		chooseOP2(tail-head);
	}
	return 0;
}

补充测试的数据

输入1

3
22 4 22

输出1

1 : 0
2 : 0
3 : 0
4 : 0
5 : 1
6 : 1
7 : 1
8 : 1
9 : 2
10 : 2
11 : 2
12 : 2
13 : 2
14 : 3
15 : 3
16 : 3
17 : 3
18 : 3
19 : 4
20 : 4
21 : 4
22 : 4
23 : 4
24 : 4
25 : 4
26 : 5
27 : 4
28 : 4
29 : 5
30 : 5
31 : 5
32 : 6
33 : 6
34 : 6
35 : 7
36 : 7
37 : 7
38 : 8
39 : 8
40 : 8
41 : 9
42 : 9
43 : 9
44 : 10
45 : 10
46 : 10
47 : 11
48 : 11

补充测试数据解析

周期1:队列22人，窗口开放4个，服务1~4号

周期2:队列22人，窗口开放4个，服务5~8号

周期3:队列40人，窗口开放5个，服务9~13号

周期4:队列35人，开放窗口5个，服务14~18号

周期5:队列30人，开放窗口4个，服务19~22号