数据结构作业&实验：银行排队问题系列问题题解

xiin 2025-10-10 09:45 37 阅读56分钟

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

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

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

输入格式:

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

输出格式:

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

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

输入样例：

输出样例：

6.2 17 61
5 3 1

题解：

#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;
}

7-3 银行业务队列简单模拟

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

输入格式:

输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15

题解：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    int cus;
    queue<int> a;
    queue<int> b;
    for (int i = 0; i < n; i++) {
        cin >> cus;
        if (cus % 2 == 0) b.push(cus);
        else a.push(cus);
    }
    bool flag = false;
    while (!a.empty() || !b.empty()) {
        if (!a.empty()) {
            if (flag) cout << " ";
            cout << a.front();
            a.pop();
            flag = true;
        }
        if (!a.empty()) {
            if (flag) cout << " ";
            cout << a.front();
            a.pop();
            flag = true;
        }
        if (!b.empty()) {
            if (flag) cout << " ";
            cout << b.front();
            b.pop();
            flag = true;
        }
    }
}

7-4 银行排队问题之单窗口“夹塞”版

排队“夹塞”是引起大家强烈不满的行为，但是这种现象时常存在。在银行的单窗口排队问题中，假设银行只有1个窗口提供服务，所有顾客按到达时间排成一条长龙。当窗口空闲时，下一位顾客即去该窗口处理事务。此时如果已知第i位顾客与排在后面的第j位顾客是好朋友，并且愿意替朋友办理事务的话，那么第i位顾客的事务处理时间就是自己的事务加朋友的事务所耗时间的总和。在这种情况下，顾客的等待时间就可能被影响。假设所有人到达银行时，若没有空窗口，都会请求排在最前面的朋友帮忙（包括正在窗口接受服务的朋友）；当有不止一位朋友请求某位顾客帮忙时，该顾客会根据自己朋友请求的顺序来依次处理事务。试编写程序模拟这种现象，并计算顾客的平均等待时间。

输入格式:

输入的第一行是两个整数：1≤N≤10000，为顾客总数；0≤M≤100，为彼此不相交的朋友圈子个数。若M非0，则此后M行，每行先给出正整数2≤L≤100，代表该圈子里朋友的总数，随后给出该朋友圈里的L位朋友的名字。名字由3个大写英文字母组成，名字间用1个空格分隔。最后N行给出N位顾客的姓名、到达时间T和事务处理时间P（以分钟为单位），之间用1个空格分隔。简单起见，这里假设顾客信息是按照到达时间先后顺序给出的（有并列时间的按照给出顺序排队），并且假设每个事务最多占用窗口服务60分钟（如果超过则按60分钟计算）。

输出格式:

按顾客接受服务的顺序输出顾客名字，每个名字占1行。最后一行输出所有顾客的平均等待时间，保留到小数点后1位。

输入样例:

6 2
3 ANN BOB JOE
2 JIM ZOE
JIM 0 20
BOB 0 15
ANN 0 30
AMY 0 2
ZOE 1 61
JOE 3 10

输出样例:

JIM
ZOE
BOB
ANN
JOE
AMY
75.2

题解：

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <iomanip>
using namespace std;

const int MAXN = 10010;

struct Customer {
    string name;
    int arrive;
    int service;
    int wait;
    bool visited;
};

int parent[MAXN];
vector<string> groups[110];
Customer customers[MAXN];
map<string, int> nameToIndex;
queue<Customer> q;

int find(int x) {
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

int main() {
    int m, n, k;
    cin >> m >> n;

    // 初始化并查集
    for (int i = 0; i < m; i++) {
        parent[i] = i;
    }

    // 输入朋友圈
    for (int i = 0; i < n; i++) {
        cin >> k;
        groups[i].resize(k);
        for (int j = 0; j < k; j++) {
            cin >> groups[i][j];
        }
    }

    // 输入客户信息
    for (int i = 0; i < m; i++) {
        cin >> customers[i].name >> customers[i].arrive >> customers[i].service;
        if (customers[i].service > 60) {
            customers[i].service = 60;
        }
        customers[i].wait = 0;
        customers[i].visited = false;
        nameToIndex[customers[i].name] = i;
    }

    // 建立朋友圈关系
    for (int i = 0; i < n; i++) {
        if (groups[i].empty()) continue;
        int first = nameToIndex[groups[i][0]];
        for (size_t j = 1; j < groups[i].size(); j++) {
            int member = nameToIndex[groups[i][j]];
            unionSets(first, member);
        }
    }

    // 处理服务顺序
    int currentId = 0;
    customers[0].visited = true;
    customers[0].wait = 0;
    q.push(customers[0]);
    int endTime = customers[0].arrive + customers[0].service;

    while (q.size() < m) {
        bool foundFriend = false;

        // 先找可以加塞的朋友
        for (int i = 1; i < m; i++) {
            if (customers[i].visited) continue;
            if (find(i) == find(currentId) && customers[i].arrive <= endTime) {
                customers[i].visited = true;
                customers[i].wait = endTime - customers[i].arrive;
                q.push(customers[i]);
                endTime += customers[i].service;
                currentId = i;
                foundFriend = true;
                break;
            }
        }

        if (foundFriend) continue;

        // 找下一个普通客户
        for (int i = 1; i < m; i++) {
            if (customers[i].visited) continue;
            customers[i].visited = true;
            q.push(customers[i]);

            if (customers[i].arrive <= endTime) {
                customers[i].wait = endTime - customers[i].arrive;
                endTime += customers[i].service;
            } else {
                customers[i].wait = 0;
                endTime = customers[i].arrive + customers[i].service;
            }
            currentId = i;
            break;
        }
    }

    // 输出结果
    while (!q.empty()) {
        cout << q.front().name << endl;
        q.pop();
    }

    double totalWait = 0;
    for (int i = 0; i < m; i++) {
        totalWait += customers[i].wait;
    }
    cout << fixed << setprecision(1) << totalWait / m << endl;

    return 0;
}

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

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

输入格式:

输出格式:

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

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

输入样例：

输出样例：

6.2 17 61
5 3 1

题解：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Customer {
    int arrive;
    int process;
    int wait;
};

int main() {
    int n, k;
    cin >> n;

    vector<Customer> customers(n);
    for (int i = 0; i < n; i++) {
        cin >> customers[i].arrive >> customers[i].process;
        if (customers[i].process > 60) {
            customers[i].process = 60;
        }
    }
    cin >> k;

    vector<int> window(k, 0);      // 窗口剩余处理时间
    vector<int> serve_count(k, 0); // 各窗口服务人数
    int front = 0;                 // 当前要处理的客户索引
    int max_wait = 0;              // 最大等待时间
    int total_wait = 0;            // 总等待时间
    int current_time = 0;          // 当前时间

    while (true) {
        // 更新所有窗口状态
        for (int i = 0; i < k; i++) {
            if (window[i] > 0) {
                window[i]--;
            }
        }

        // 计算当前等待的客户数
        for (int i = front; i < n; i++) {
            if (customers[i].arrive < current_time) {
                total_wait++;
            }
        }

        // 分配客户到空闲窗口
        for (int i = 0; i < k; i++) {
            if (window[i] == 0 && front < n) {
                if (customers[front].arrive > current_time) break;

                customers[front].wait = current_time - customers[front].arrive;
                max_wait = max(max_wait, customers[front].wait);
                serve_count[i]++;
                window[i] = customers[front].process;
                front++;
            }
        }

        // 检查是否所有客户都处理完毕
        int remaining_time = 0;
        for (int i = 0; i < k; i++) {
            remaining_time += window[i];
        }
        if (remaining_time == 0 && front == n) break;

        current_time++;
    }

    printf("%.1lf %d %d\n", total_wait * 1.0 / n, max_wait, current_time);
    for (int i = 0; i < k; i++) {
        if (i > 0) cout << " ";
        cout << serve_count[i];
    }
    cout << endl;

    return 0;
}

7-6 银行排队问题之单队列多窗口加VIP服务

有些银行会给VIP客户以各种优惠服务，例如专门开辟VIP窗口。为了最大限度地利用资源，VIP窗口的服务机制定义为：当队列中没有VIP客户时，该窗口为普通顾客服务；当该窗口空闲并且队列中有VIP客户在等待时，排在最前面的VIP客户享受该窗口的服务。同时，当轮到某VIP客户出列时，若VIP窗口非空，该客户可以选择空闲的普通窗口；否则一定选择VIP窗口。

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

输入格式:

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

输出格式:

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

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

输入样例：

输出样例：

15.1 35 67
4 5 1

题解：

#include <stdio.h>
#include <string.h>
typedef struct {
    int t,p,flag;
} Queue;
Queue Q[1010];
void ChkVip(int start,int end,int sum) {
    int i,pos;
    for(i=start; i<end; i++) {
        if(Q[i].flag==1&&Q[i].t<sum) {//查看是否有VIP客户已经在等待
            pos=i;
            break;
        }
    }
    if(i<end) {//VIP客户插队
        Queue tmp=Q[pos];
        for(i=pos-1; i>=start; i--) {
            Q[i+1]=Q[i];
        }
        Q[start]=tmp;
    }
}
int main() {
    int n,i,min;
    scanf("%d",&n);
    int front=0,rear=0;
    for(i=0; i<n; i++) {
        scanf("%d %d %d",&Q[rear].t,&Q[rear].p,&Q[rear].flag);
        if(Q[rear].p>60)Q[rear].p=60;
        rear++;
    }
    int k,c;
    scanf("%d %d",&k,&c);
    int sum[k],winnum[k];
    memset(sum,0,sizeof(sum));
    memset(winnum,0,sizeof(winnum));
    int SWT=0,WT=0,LWT=0;
    while(front<rear) {
        if(Q[front].flag==0) {//队头是普通客户
            min=0;
            for(i=0; i<k; i++) {//查找空闲窗口
                if(Q[front].t>=sum[i]) {//此时无需等待
                    if(i==c)//当前空闲窗口是VIP窗口，则查找此时是否有Vip客户已经到时来，若vip已经到来，则将vip插队上来
                        ChkVip(front,n,sum[i]);
                    sum[i]=Q[front].t+Q[front].p;
                    front++;
                    winnum[i]++;
                    break;
                }
                if(sum[i]<sum[min])
                    min=i;
            }
            if(i==k) {//已经到来在等待
                if(min==c)//当前空闲窗口是VIP窗口，则查找此时是否有Vip客户已经到时来，若vip已经到来，则将vip插队上来
                    ChkVip(front,n,sum[min]);
                WT=sum[min]-Q[front].t;
                if(WT>LWT)LWT=WT;
                SWT+=WT;
                sum[min]+=Q[front].p;
                front++;
                winnum[min]++;

            }
        } else {//队头是VIP客户
            if(Q[front].t>=sum[c]) {//查找此时是否有VIP窗口空闲
                sum[c]=Q[front].t+Q[front].p;
                winnum[c]++;
                front++;
            } else {
                min=c;
                for(i=0; i<k; i++) {//查找最快完成窗口
                    if(sum[i]<sum[min])
                        min=i;
                }
                if(Q[front].t>=sum[min])//无需等待
                    sum[min]=Q[front].t+Q[front].p;
                else {//需等待
                    WT=sum[min]-Q[front].t;
                    if(WT>LWT)LWT=WT;
                    SWT+=WT;
                    sum[min]+=Q[front].p;
                }
                front++;
                winnum[min]++;
            }
        }
    }
    int LFT=0;
    for(i=0; i<k; i++) {
        if(sum[i]>sum[LFT])
            LFT=i;
    }
    printf("%.1lf %d %d\n",(double)SWT/n,LWT,sum[LFT]);
    for(i=0; i<k; i++) {
        if(i>0)
            printf(" ");
        printf("%d",winnum[i]);
    }
    return 0;
}

数据结构作业&实验：银行排队问题系列问题题解

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

输入格式:

输出格式:

输入样例：

输出样例：

题解：

7-3 银行业务队列简单模拟

输入格式:

输出格式:

输入样例:

输出样例:

题解：

7-4 银行排队问题之单窗口“夹塞”版

输入格式:

输出格式:

输入样例:

输出样例:

题解：

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

输入格式:

输出格式:

输入样例：

输出样例：

题解：

7-6 银行排队问题之单队列多窗口加VIP服务

输入格式:

输出格式:

输入样例：

输出样例：

题解：

评论

最新文章

目录

下一篇

目录

登录

数据结构作业&实验：银行排队问题系列问题题解

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

输入格式:

输出格式:

输入样例：

输出样例：

题解：

7-3 银行业务队列简单模拟

输入格式:

输出格式:

输入样例:

输出样例:

题解：

7-4 银行排队问题之单窗口“夹塞”版

输入格式:

输出格式:

输入样例:

输出样例:

题解：

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

输入格式:

输出格式:

输入样例：

输出样例：

题解：

7-6 银行排队问题之单队列多窗口加VIP服务

输入格式:

输出格式:

输入样例：

输出样例：

题解：

评论

相关推荐

KMP 算法笔记

数据结构作业题：列车调度 —— 最长递增子序列

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

数据结构作业题：表达式转换（中缀转后缀） —— 栈

数据结构作业题：汉诺塔的非递归实现

【数据结构与算法】并查集模板

【数据结构与算法】二叉查找树的操作

【数据结构与算法】二叉堆的 4 种操作

【数据结构与算法】根据后序和中序遍历输出前序遍历

【数据结构与算法】根据 前序遍历序列和中序遍历序列 还原二叉树

最新文章

目录

下一篇

目录

【数据结构与算法】根据前序遍历序列和中序遍历序列还原二叉树