PTA
排隊“夾塞”是引起大家強烈不滿的行為，但是這種現(xiàn)象時常存在。在銀行的單窗口排隊問題中，假設銀行只有1個窗口提供服務，所有顧客按到達時間排成一條長龍。當窗口空閑時，下一位顧客即去該窗口處理事務。此時如果已知第i位顧客與排在后面的第j位顧客是好朋友，并且愿意替朋友辦理事務的話，那么第i位顧客的事務處理時間就是自己的事務加朋友的事務所耗時間的總和。在這種情況下，顧客的等待時間就可能被影響。假設所有人到達銀行時，若沒有空窗口，都會請求排在最前面的朋友幫忙（包括正在窗口接受服務的朋友）；當有不止一位朋友請求某位顧客幫忙時，該顧客會根據(jù)自己朋友請求的順序來依次處理事務。試編寫程序模擬這種現(xiàn)象，并計算顧客的平均等待時間。

輸入格式:

輸入的第一行是兩個整數(shù)：1≤N≤10000，為顧客總數(shù)；0≤M≤100，為彼此不相交的朋友圈子個數(shù)。若M非0，則此后M行，每行先給出正整數(shù)2≤L≤100，代表該圈子里朋友的總數(shù)，隨后給出該朋友圈里的L位朋友的名字。名字由3個大寫英文字母組成，名字間用1個空格分隔。最后N行給出N位顧客的姓名、到達時間T和事務處理時間P（以分鐘為單位），之間用1個空格分隔。簡單起見，這里假設顧客信息是按照到達時間先后順序給出的（有并列時間的按照給出順序排隊），并且假設每個事務最多占用窗口服務60分鐘（如果超過則按60分鐘計算）。

輸出格式:

按顧客接受服務的順序輸出顧客名字，每個名字占1行。最后一行輸出所有顧客的平均等待時間，保留到小數(shù)點后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 <bits/stdc++.h> //雙向鏈表實現(xiàn)，本題還有一個更好的優(yōu)化方法，可以通過記錄朋友屬性的次數(shù)來忽略不必要的搜索 using namespace std; typedef struct consumer {char name[5];double arrive;double start;double process;double end;double wait;struct consumer *next; //朋友找人幫忙看的是end，輸出看的是start. struct consumer *prior; }List; int main() {int n,m;char name[5];int record[60][60][60]={0}; //這個數(shù)組每一個下標代表著名字的每一個字母，數(shù)組元素存放著共同屬性---是不是朋友，一種更為簡單的方法是使用map函數(shù)List *head=NULL,*tail,*p; //本機調(diào)試不減65很容易段錯誤，可能是三維數(shù)組的特性？cin>>n>>m;for (int i=1;i<=m;i++) //輸入朋友圈 {int k;cin>>k;for (int j=0;j<k;j++){getchar();scanf("%s",name);record[name[0]-65][name[1]-65][name[2]-65]=i;}}double arrive,process,lastendtime=0;for (int i=0;i<n;i++) //每個人的信息并在輸入的過程中查看前面有沒有朋友 { //有沒有朋友指自己的到達時間比朋友離開的時間要早，即下面的判斷條件 int flag=0; //record[temp->name[0]-65][temp->name[1]-65][temp->name[2]-65]==record[p->name[0]-65][p->name[1]-65][p->name[2]-65]&&p->arrive<=temp->endscanf("%s%lf%lf",name,&arrive,&process);if (process>60) process=60;p=(List *)malloc(sizeof(List)); //為朋友節(jié)點賦值 p->next=NULL;p->prior=NULL;strcpy(p->name,name);p->arrive=arrive;p->process=process;if (i==0) //第一個人一定是一來就被處理 {p->start=p->arrive;}else //lastendtime是窗口的availiable的時間 {if (p->arrive<=lastendtime) //到的時間比availiable時間早，那么需要等一會，一有空就去處理 p->start=lastendtime;else //這是窗口有一段空的時間，來了就處理，同時要注意下邊56行對lastendtime的刷新 p->start=p->arrive;}p->end=p->start+p->process; //結束時間 lastendtime=p->end; //刷新 p->wait=p->start-p->arrive; //計算此人的等待時間 if (p->wait<0) p->wait=0; //如果等待時間為負，那么說明來的比lastendtime晚，沒等待（注：實際上，53行已考慮了） if (head==NULL) //插入 {head=p;tail=p; //別忘了，不然后面的插入會發(fā)生段錯誤 }else{for (List *temp=tail;temp!=NULL;temp=temp->prior) //找朋友 {if (record[temp->name[0]-65][temp->name[1]-65][temp->name[2]-65]==record[p->name[0]-65][p->name[1]-65][p->name[2]-65]&&p->arrive<=temp->end) //temp處是要插入的前一個位置 { //如果二人屬性相同并且后來者是趕在朋友走之前來的 flag=1; //需要在前面插入 for (List *rr=temp->next;rr!=NULL;rr=rr->next) //temp是他的朋友，在這個人加塞后，后面的每個人都要 { //加時長 rr->start+=p->process;rr->end+=p->process;rr->wait=rr->start-rr->arrive;if (rr->wait<=0) rr->wait=0;}if (temp->next==NULL) //樣例中BOB和ANN的情況，如果朋友也在最后，那么tail要移動到這個人 {tail=p;}p->start=temp->end; //朋友的結束就是此人的開始 p->end=p->start+p->process; //刷新此人的所有信息（82-84） p->wait=p->start-p->arrive;if (p->wait<0) p->wait=0;p->next=temp->next;if (temp->next!=NULL) //連接，畫圖理解 temp->next->prior=p;p->prior=temp;temp->next=p;break;}}if (flag==0) //此人沒有找到朋友，可憐，只能尾插 {p->prior=tail;tail->next=p;tail=p;}}}for (List *tt=head;tt!=NULL;tt=tt->next) //輸出名字 {printf("%s\n",tt->name);}double sum=0;for (List *temp=head;temp!=NULL;temp=temp->next) //計算總等待時間 { sum+=temp->wait;}printf("%.1lf",sum/n);return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的7-2 银行排队问题之单窗口“夹塞”版 (30 分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。