【PAT甲级】1014 Waiting in Line (30 分)

1014 Waiting in Line

题目描述

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

• The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.

• Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.

• Customer_i will take T_i minutes to have his/her transaction processed.

• The first N customers are assumed to be served at 8:00am.

Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 custmers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer​₁ is served at window​₁ while customer​₂ is served at window​₂. Customer​₃ will wait in front of window​₁ and customer​₄ will wait in front of window₂. Customer​₅ will wait behind the yellow line.

At 08:01, customer​₁ is done and customer​₅​ enters the line in front of window​₁​ since that line seems shorter now. Customer​₂​ will leave at 08:02, customer​₄ at 08:06, customer​₃ at 08:07, and finally customer​₅ at 08:10.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (≤20, number of windows), M (≤10, the maximum capacity of each line inside the yellow line), K (≤1000, number of customers), and Q (≤1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output Specification:

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output Sorry instead.

Sample Input:

2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

Sample Output:

08:07
08:06
08:10
17:00
Sorry

思路：

本题属于一个模拟题，第一次做可能比较难想，需要使用N个队列的数据结构来存储队伍信息。同时模拟根据时间推移而进行。
注意首先M*N个人依次进入窗口排队，之后的人在黄线外等待，一旦某一个时刻有人结束业务，就可以进入一个人。

坑点：题目说银行17:00下班，但是对于17点前接待的业务（不包括17点），无论处理时间多长，都要处理完成

首先定义了一个结构体，用于储存每一个人的信息

struct people
{
	int ID;
	int PT;//处理时间
	int ED;//结束时间
};

定义的全局变量与函数

vector<people> store(MAX);//存储每一个人的初始信息
vector<int> request(MAX);//存储最后要求输出的人的序号
int N,M,K,Q;

void input();//输入函数
void start();//模拟函数
void print_time(int ED);//根据结束时间输出函数
void process();//输出所有要求的人的结果

输入数据，注意初始时将每一个人的结束时间设为0

void input()
{
	scanf("%d %d %d %d",&N,&M,&K,&Q);
	for(int i=1;i<=K;i++)//将K个人放入store数组中1-K
	{
		store[i].ID=i;
		scanf("%d",&store[i].PT);
		store[i].ED=0;//将每一个人的结束时间设为0
	}
	for(int i=0;i<Q;i++)
	{
		scanf("%d",&request[i]);
	}
	return;
}

模拟过程的函数start

其中Bank是存储N个队列的数组，head是标记黄线外第一个人的序号。初始时先将M*N个人入到N个队列中，同时将每一个队列头元素的结束时间设为该人的处理时间，并更新store数组该人的信息。

之后开始进行模拟，从早上八点开始到下午五点，time从0开始到540，九个小时，不包括540。
每一个时刻依次对每一个队的队首元素进行检查，如果该人的结束时间为当前的time，证明该人业务处理完成，将其弹出队列，这时可以从黄线外立刻补充一个人进入该队列（由于每次遍历都是从小序号的窗口开始检索，因此即使两个队列人数一样，也满足优先进入序号小的队伍），同时每弹出一个人，将该队列新的队首元素的结束时间更新为time+PT

void start()
{
	vector<queue<people>> Bank(N);
	int head=1;
	for(int j=0;j<M;j++)//初始将M*N人放入队列
	{
		for(int i=0;i<N;i++)
		{
			if(head>K)break;
			Bank[i].push(store[head++]);
		}
	}
	for(int i=0;i<N;i++)//初始时候每个队第一个人离开的时间就是他的处理时间
	{
		if(Bank[i].empty())
			continue;
		Bank[i].front().ED=Bank[i].front().PT;
		store[Bank[i].front().ID].ED=Bank[i].front().ED;//更新store数组该人的信息
	}
	for(int time=0;time<540;time++)//从早上八点到下午五点,如果到了五点就不再服务客户了
	{
		for(int i=0;i<N;i++)
		{
			if(Bank[i].empty())
				continue;
			if(Bank[i].front().ED==time)//如果该时间有人结束，证明可以进入新的人
			{
				Bank[i].pop();//弹出一个人
				if(head<=K)//每弹出一个人，证明可以进入新的人
				{
					//由于每个时间点是从小窗口开始遍历，如果有新的人进入也是从小窗口进入
					Bank[i].push(store[head++]);//进入一个新的人
				}
				if(!Bank[i].empty())//如果进入了新的人，更新队列头的人的结束时间
				{
					Bank[i].front().ED=time+Bank[i].front().PT;
					store[Bank[i].front().ID].ED=Bank[i].front().ED;
				}
			}
		}
	}
	return;
}

当模拟结束，处理过的人的结束时间都进行了更新（不为0），为0的表示没有处理到，根据每一个人的结束时间输出的函数定义如下

void print_time(int ED)
{
	if(ED==0)
	{
		printf("Sorry\n");
		return;
	}
	int h,m;
	h=ED/60;
	m=ED%60;
	h+=8;
	printf("%02d:%02d\n",h,m);
	return;
}

最后从输出要求输出的人的信息

void process()
{
	for(int i=0;i<Q;i++)
	{
		print_time(store[request[i]].ED);
	}
	return;
}

主函数：

int main()
{
	input();
	start();
	process();
	return 0;
}

代码

//1014 Waiting in Line
#include<stdio.h>
#include<queue>
#include<vector>

#define MAX 1001

using namespace std;

struct people
{
	int ID;
	int PT;//处理时间
	int ED;//结束时间
};

vector<people> store(MAX);
vector<int> request(MAX);
int N,M,K,Q;

void input();
void start();
void print_time(int ED);
void process();

int main()
{
	input();
	start();
	process();
	return 0;
}

void input()
{
	scanf("%d %d %d %d",&N,&M,&K,&Q);
	for(int i=1;i<=K;i++)
	{
		store[i].ID=i;
		scanf("%d",&store[i].PT);
		store[i].ED=0;
	}
	for(int i=0;i<Q;i++)
	{
		scanf("%d",&request[i]);
	}
	return;
}

void start()
{
	vector<queue<people>> Bank(N);
	int head=1;
	for(int j=0;j<M;j++)//初始将M*N人放入队列
	{
		for(int i=0;i<N;i++)
		{
			if(head>K)break;
			Bank[i].push(store[head++]);
		}
	}
	for(int i=0;i<N;i++)//初始时候每个队第一个人离开的时间就是他的处理时间
	{
		if(Bank[i].empty())
			continue;
		Bank[i].front().ED=Bank[i].front().PT;
		store[Bank[i].front().ID].ED=Bank[i].front().ED;
	}
	for(int time=0;time<540;time++)//从早上八点到下午五点,如果到了五点就不再服务客户了
	{
		for(int i=0;i<N;i++)
		{
			if(Bank[i].empty())
				continue;
			if(Bank[i].front().ED==time)//如果该时间有人结束，证明可以进入新的人
			{
				Bank[i].pop();//弹出一个人
				if(head<=K)//每弹出一个人，证明可以进入新的人
				{
					//由于每个时间点是从小窗口开始遍历，如果有新的人进入也是从小窗口进入
					Bank[i].push(store[head++]);//进入一个新的人
				}
				if(!Bank[i].empty())//如果进入了新的人，更新队列头的人的结束时间
				{
					Bank[i].front().ED=time+Bank[i].front().PT;
					store[Bank[i].front().ID].ED=Bank[i].front().ED;
				}
			}
		}
	}
	return;
}

void print_time(int ED)
{
	if(ED==0)
	{
		printf("Sorry\n");
		return;
	}
	int h,m;
	h=ED/60;
	m=ED%60;
	h+=8;
	printf("%02d:%02d\n",h,m);
	return;
}

void process()
{
	for(int i=0;i<Q;i++)
	{
		print_time(store[request[i]].ED);
	}
	return;
}

git仓库:Waiting in Line