题目描述：设计一个银行业务模拟系统，模拟银行的业务运行并计算一天中客户在银行逗留的平均时间。银行有N（N的取值自己定义）个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务；反之，若N个窗口均有客户所占，他便会排在人数最少的队伍后面。
基本要求：
（1）在界面上可以设定银行的对外营业时间（银行的开门时间以及银行的关门时间）。
（2）用人机交互的方式来输入客户的到达时间以及客户的业务处理时间，用队列来存储客户的到达事件和客户的离开事件。
（3）可以友好的显示出在某一天中整个银行系统中客户在银行逗留的平均时间。
解题思路：类似银行取号系统：比如：哪怕之前某个时刻看似排队在1号窗口（人数最少）最快，但是中途发现其他窗口更快，可以随时调离，取最优情况。
代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a) #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct P { int sh,sm,ss; // * 进入时间 int eh,em,es; // * 离开时间 int ssum,esum; // 进入时间(s) 离开时间(s) int ds,ws; // 处理时间deal(s) 等候时间(s) }; int cmp(P p1,P p2) // * { return p1.ssum<p2.ssum; } int cmp2(P p1,P p2) // * { return p1.esum<p2.esum; } struct pq_cmp // 根据先到达的人先处理业务 { bool operator()(P p1,P p2) { return p1.ssum>p2.ssum; // 进入的时间：从小到大 } }; struct dpq_cmp // 根据先离开的人先交接并计算结果 { bool operator()(P p1,P p2) { return p1.esum>p2.esum; // 离开的时间：从小到大 } }; // 优先队列 // dpq作用：主要用来与下一个交接窗口的人的时间差维护，方便下次加入dpq时， // 判断谁先出来（即哪个窗口先为空），计算该人离开的逗留时间和。 priority_queue<P,vector<P>,pq_cmp> pq; // 存储入队的人优先到达银行的排在Top priority_queue<P,vector<P>,dpq_cmp> dpq; // 存储入队的人优先离开银行的排在Top int h1,m1,s1,h2,m2,s2,n; // 银行营业时间 窗口数 void init() // 初始化 { while(!pq.empty()) pq.pop(); while(!dpq.empty()) dpq.pop(); } void showBankTime() { printf("Bank OpenTime：\n"); printf("%02d:%02d A.M.\n",h1,m1); printf("%02d:%02d P.M.\n\n",h2,m2); } int main() { printf("Please input Bank OpenTime (hh:mm:ss): "); while(~scanf("%d:%d:%d %d:%d:%d",&h1,&m1,&s1,&h2,&m2,&s2)) { printf("Please input Bank Windows Count: "); scanf("%d",&n); printf("\n-----------Start-----------\n"); init(); showBankTime(); int sum,len; sum=len=0; // sum：所有客户逗留时间 len：客户总数 int sh,sm,ss,ds; // 客户进入银行时间 客户处理业务所需时间 P ps[1000]; // * printf("Ps: Button Ctrl + Z as input end!\n"); printf("Please input People ArriveTime(hh:mm:ss) and DealTime(s):\n"); while(~scanf("%d:%d:%d %d",&sh,&sm,&ss,&ds)) // Crtl + Z == break { P tp; tp.ds=ds; tp.esum=tp.ssum=sh*3600+sm*60+ss; tp.esum+=ds; tp.ws=0; tp.sh=sh; tp.sm=sm; tp.ss=ss; // * pq.push(tp); ps[len]=tp; // * len++; printf("Please input People ArriveTime(hh:mm:ss) and DealTime(s):\n"); } // printf("-------PQueue------\n"); // * // for(int i=0;i<len;i++) // * // { // P tp=pq.top(); pq.pop(); // printf("P%d:\n",i); // printf("SH:SM:SS : %d:%d:%d\n",tp.sh,tp.sm,tp.ss); // printf("SSUM : %d\n",tp.ssum); // printf("DS : %d\n\n",tp.ds); // } // printf("-------PQueue------\n"); // * // sort(ps,ps+len,cmp); // * // printf("-------------------\n"); // * // printf("\nPNum == %d\n\n",len); // * // for(int i=0;i<len;i++) // * // { // P tp=ps[i]; // printf("P%d:\n",i); // printf("SH:SM:SS : %d:%d:%d\n",tp.sh,tp.sm,tp.ss); // printf("SSUM : %d\n",tp.ssum); // printf("WS : %d\n",tp.ws); // printf("DS : %d\n\n",tp.ds); // } // printf("-------------------\n"); // * for(int i=0;i<n;i++) // 补满第一批一开始空的窗口 { dpq.push(pq.top()); pq.pop(); } int k=0; // * while(!pq.empty()) // 即将进入dpq的预备队列pq里如果没有客户，即可退出 { P tdpq=dpq.top(); // 最早离开银行的客户 // * // printf("%dth:\n",k); // P tp=tdpq; // printf("SH:SM:SS : %d:%d:%d\n",tp.sh,tp.sm,tp.ss); // printf("SSUM : %d\n",tp.ssum); // printf("DS : %d\n",tp.ds); // printf("WS : %d\n",tp.ws); // int tp_esum=tp.esum; // tp.eh=tp_esum/3600; tp.em=(tp_esum%3600)/60; tp.es=tp_esum%60; // printf("EH:EM:ES : %d:%d:%d\n",tp.eh,tp.em,tp.es); // printf("ESUM : %d\n\n",tp.esum); ps[k++]=tdpq; // * dpq.pop(); P tpq=pq.top(); // 下一个最早进入银行的客户 // 判断是否下个客户需要等待 if(tdpq.esum>tpq.ssum) // 需等待 { tpq.ws=tdpq.esum-tpq.ssum; // 即将进入窗口(下个客户)的等待时间 tpq.esum+=tpq.ws; // 提前计算出即将进入窗口(下个客户)离开的时间 } // else // 无需等待，此处else代码可以省略，因为初始化的时候就是默认该值 // { // tpq.ws=0; // tpq.esum+=tpq.ws; // } sum+=tdpq.esum-tdpq.ssum; // 计算该离开客户的时间差 // printf("sum == %d\n\n",sum); // * dpq.push(tpq); pq.pop(); } while(!dpq.empty()) // 如果dpq里还有剩余的客户，进行最后计算处理 { P tdpq=dpq.top(); ps[k++]=tdpq; // * dpq.pop(); sum+=tdpq.esum-tdpq.ssum; // * // printf("%dth:\n",k); // P tp=tdpq; // printf("SH:SM:SS : %d:%d:%d\n",tp.sh,tp.sm,tp.ss); // printf("SSUM : %d\n",tp.ssum); // printf("DS : %d\n",tp.ds); // printf("WS : %d\n",tp.ws); // int tp_esum=tp.esum; // tp.eh=tp_esum/3600; tp.em=(tp_esum%3600)/60; tp.es=tp_esum%60; // printf("EH:EM:ES : %d:%d:%d\n",tp.eh,tp.em,tp.es); // printf("ESUM : %d\n\n",tp.esum); // printf("sum == %d\n\n",sum); // * } // sort(ps,ps+k,cmp2); // * // printf("-------------------\n"); // * // printf("\nOutNum == %d\n\n",k); // * // for(int i=0;i<k;i++) // * // { // P tp=ps[i]; // printf("P%d:\n",i); // printf("SH:SM:SS : %d:%d:%d\n",tp.sh,tp.sm,tp.ss); // printf("SSUM : %d\n",tp.ssum); // printf("DS : %d\n",tp.ds); // printf("WS : %d\n",tp.ws); // int tp_esum=tp.esum; // tp.eh=tp_esum/3600; tp.em=(tp_esum%3600)/60; tp.es=tp_esum%60; // printf("EH:EM:ES : %d:%d:%d\n",tp.eh,tp.em,tp.es); // printf("ESUM : %d\n\n",tp.esum); // } // printf("-------------------\n"); // * printf("\nAll People Num: %d\n",len); printf("All time: %d s\n",sum); printf("Avg time: %.2lf s\n",sum*1.0/len); printf("\n-----------END-----------\n\n"); printf("Please input Bank OpenTime: "); } return 0; }
