一：題目

排隊“夾塞”是引起大家強烈不滿的行為，但是這種現象時常存在。在銀行的單窗口排隊問題中，假設銀行只有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

二：思路

首先在選擇數據結構上，這個用到結構體，即一個下標可以表示多個變量（本題中的名字，和到達時間，事務辦理時間，可惜我沒想到呀），然后在處理朋友圈上，用到了map容器，即一個朋友圈內朋友有相同的編號；
還有要說的是，這個題中的是時間，要當成是時間軸上的數據（很重要，便于理解）；

三：上碼

#include<bits/stdc++.h> using namespace std;struct Node{string name;int arrive;//到達時間int transaction;//事務辦理時間 }node;int main(){int N,M;map<string,int>m;Node *stu = new Node[10020];int visited[10020] = {0};cin >> N >> M;for(int i = 1; i <= M; i++){int temp;cin >> temp;for(int j = 1; j <= temp; j++){string name;cin >> name;m[name] = i;}}for( int i = 1; i <= N; i++){cin >> stu[i].name >> stu[i].arrive >> stu[i].transaction;stu[i].transaction = stu[i].transaction > 60 ? 60:stu[i].transaction; }int manage = 0;//窗口的辦理時間int total_wait = 0;//總共的等待時間for( int i = 1; i <= N; i++){if(visited[i] == 0){visited[i] = 1;//如果到達時間 大于窗口的事務辦理時間 即可 直接進行辦理事務 if(stu[i].arrive > manage){manage = stu[i].arrive + stu[i].transaction;//更新窗口的事務辦理時間 }else{//窗口有人在辦理事務，所以需要等待 total_wait += manage - stu[i].arrive;manage += stu[i].transaction;} cout << stu[i].name << endl;//判斷后面是否有朋友for(int j = i + 1; j <= N; j++){//如果你的朋友在你的后面第一位，那么他就可以等你走后直接辦理 if( stu[j].arrive > manage){break;}if(m[stu[i].name] == m[stu[j].name] && visited[j] == 0){visited[j] = 1;total_wait += manage - stu[j].arrive;manage += stu[j].transaction;cout << stu[j].name << endl; } } }} //cout << 1.0 * total_wait / N << endl;printf("%0.1f",1.0 * total_wait / N);}

加油陌生人！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

總結

以上是生活随笔為你收集整理的7-48 银行排队问题之单窗口“夹塞”版 (30 分)(思路和详解+map做法)来呀Baby!的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。