银行排队问题之单队列多窗口服务 C++ 数据结构
题目描述
假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。
本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。
输入
输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。
输出
在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。
在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。
输入样例1
9 0 20 1 15 1 61 2 10 10 5 10 3 30 18 31 25 31 2 3
输出样例1
6.2 17 61 5 3 1
思路分析
我们先把客户读取进来，用一个队列去装，先把办理时间超过60的改成60，然后压进去。
之后我们把各个窗口的服务人数和服务时间清空，让它们都等于0。
然后开始我们令人窒息的操作：
我们从人的角度去思考（这个思维非常关键），整个处理过程在一个大循环之下进行，我们用NOW—TIME记录当前时间，从0开始，每次大循环之后自增，每次大循环后，我们让每个窗口的服务时间自减，这个大循环跳出的条件是队列为空并且所有窗口的服务时间为0。
然后在大循环内部，去判断有没有人来了（队列非空），人是不是到了（到达时间小于等于现在的时间），然后挨个查看窗口有没有空（该窗口服务时间为0），有空就去，对应窗口服务时间更新为客户办理时间。
这里需要注意可能有多个客户同时到达，也就是说我们需要看完有没有人能去办理再让时间继续自增。
AC代码
#include <bits/stdc++.h>
using namespace std;
struct customer {
int reach_time, deal_time;
};
int main() {
int N, longest_time = 0, total_time = 0, K, NOW_TIME = 0;
cin >> N;
queue<customer> client;
for (int i = 0; i < N; i++) {
customer one;
cin >> one.reach_time >> one.deal_time;
if (one.deal_time > 60)one.deal_time = 60;
client.push(one);
}
cin >> K;
int windows_serve[K], windows_deal_time[K];
for (int i = 0; i < K; i++) {
windows_deal_time[i] = windows_serve[i] = 0;
}
while (1) {
while (!client.empty() && client.front().reach_time <= NOW_TIME) {
bool finish = false;
for (int i = 0; i < K; i++) {
if (windows_deal_time[i] == 0) {
windows_serve[i]++;
windows_deal_time[i] = client.front().deal_time;
total_time += NOW_TIME - client.front().reach_time;
if (longest_time < NOW_TIME - client.front().reach_time)longest_time = NOW_TIME -
client.front().reach_time;
client.pop();
finish = true;
break;
}
}
if (!finish)break;
}
bool done = true;
for (int i = 0; i < K; i++) {
if (windows_deal_time[i])windows_deal_time[i]--;
if (windows_deal_time[i])done = false;
}
NOW_TIME++;
if (done) break;
}
cout << fixed << setprecision(1) << total_time / (1.0 * N) << ' ' << longest_time << ' ' << NOW_TIME << endl;
for (int i = 0; i < K - 1; i++)
cout << windows_serve[i] << ' ';
cout << windows_serve[K - 1];
}腾讯云开发者
