数据结构作业题：银行排队问题之单队列多窗口服务 —— 队列

银行排队问题之单队列多窗口服务

假设银行有K个窗口提供服务，窗口前设一条黄线，所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时，下一位顾客即去该窗口处理事务。当有多个窗口可选择时，假设顾客总是选择编号最小的窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间，并且统计每个窗口服务了多少名顾客。

输入格式:

输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。

输出格式:

在第一行中输出平均等待时间（输出到小数点后1位）、最长等待时间、最后完成时间，之间用1个空格分隔，行末不能有多余空格。

在第二行中按编号递增顺序输出每个窗口服务了多少名顾客，数字之间用1个空格分隔，行末不能有多余空格。

输入样例：

9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3

输出样例：

6.2 17 61
5 3 1

题目理解

这是一个单队列多窗口的银行排队模拟问题。

• 有 N 个顾客，按到达时间顺序给出（T 到达时间，P 处理时间，最长 60 分钟）。
• 有 K 个窗口，顾客选择编号最小的空闲窗口。
• 如果所有窗口都忙，顾客在黄线后排队（单队列）。
• 当有窗口空闲时，队列中第一个顾客去该窗口。

需要输出：

1. 平均等待时间（保留 1 位小数）
2. 最长等待时间
3. 最后完成时间
4. 每个窗口服务的人数

思路

我们可以用事件模拟的方法：

• 用一个队列 queue 存储顾客（到达时间 T，处理时间 P）。
• 用一个数组 window_end_time[K] 表示每个窗口当前服务结束的时间（初始为 0）。
• 用一个数组 window_count[K] 记录每个窗口服务的人数。
• 用一个变量 current_time 表示当前时间（其实可以不用，直接用顾客到达时间推进）。
• 用一个变量 max_wait 记录最长等待时间，total_wait 记录总等待时间。

模拟过程：

1. 遍历每个顾客（按到达顺序）：

   • 找出最早空闲的窗口（结束时间 ≤ 当前顾客到达时间的窗口），如果有多个，选编号最小的。
   • 如果没有空闲窗口，顾客需要等待，选择最早结束的窗口（同样编号最小优先），计算等待时间。
   • 更新该窗口的结束时间，增加该窗口服务人数，更新等待时间统计。

注意点

• 顾客到达时，可能多个窗口空闲，选编号最小的。
• 等待时间 = 开始服务时间 - 到达时间。
• 开始服务时间 = max(到达时间, 窗口空闲时间)。
• 最后完成时间 = 所有窗口结束时间的最大值。

#include <bits/stdc++.h>
using namespace std;
struct Customer {
    int arrive;
    int process;
};
int main() {
    int N;
    cin>>N;
    queue<Customer> q;
    for (int i = 0; i < N; i++) {
        int T,P;
        cin>>T>>P;
        P = min(P,60);
        q.push({T,P});
    }
    int K;
    cin>>K;
    vector<int> win_end_time(K,0);
    vector<int> win_count(K,0);
    int sum_wait = 0;
    int max_wait = 0;
    int last_time = 0;
    while (!q.empty()) {
        Customer c = q.front();
        q.pop();
        int to = -1;
        for (int i = 0; i < K; i++) {
            if (c.arrive >= win_end_time[i]) {
                to = i;
                break;
            }
        }
        if (to != -1) {
            //win_end_time[to] += c.process;
            win_end_time[to] = c.arrive + c.process;
            win_count[to]++;
        } else {
            int min_wait_win_time = INT_MAX;
            int min_wait_win = -1;
            for (int i = 0; i < K; i++) {
                if (win_end_time[i] < min_wait_win_time) {
                    min_wait_win_time = win_end_time[i];
                    min_wait_win = i;
                }
            }
            int real_wait_time = win_end_time[min_wait_win] - c.arrive;
            sum_wait += real_wait_time;
            max_wait = max(max_wait, real_wait_time);
            
            win_end_time[min_wait_win] += c.process;
            win_count[min_wait_win]++;
            to = min_wait_win;
        }
        last_time = max(last_time, win_end_time[to]);
    }
    cout<<fixed<<setprecision(1)<<sum_wait*1.0/N;
    cout<<" "<<max_wait<<" "<<last_time<<"\n";
    for (int i = 0; i < K; i++) {
        if (i > 0) cout<<" ";
        cout<<win_count[i];
    }
    return 0;
}