1017. Queueing at Bank (25)

题目链接：https://www.patest.cn/contests/pat-a-practise/1017

---

题目大意：类比操作系统里的先来先服务

---

解题思路：

要模拟先来先服务，那么先对所有的人按照到来的先后顺序排序对排序后的所有人逐个选择窗口，计算需要等待的时间对于每个人，选择空出来最早的那个窗口接受服务，然后更新该窗口下次空闲出来的时间和该人的等待时间。 到的时候，最早要空出来的那个窗口都还没有空出来，则需要等待；否则，不需要等待

---

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; struct customer { int arrive,serve;//用秒来表示 }cus[10000]; bool cmp1(customer a,customer b){ return a.arrive<b.arrive;//按照到达的时间排序 } int main(int argc, char const *argv[]) { /* code */ int N,K; cin>>N>>K; int hh,mm,ss,servemm; for(int i=0;i<N;i++){ scanf("d:d:d %d",&hh,&mm,&ss,&servemm); cus[i].arrive=hh*3600+mm*60+ss;//到达时间 if(servemm>60) servemm=60; cus[i].serve=servemm*60;//服务时间 } sort(cus,cus+N,cmp1); int opentime=8*3600,endtime=17*3600; int window[K];//保存窗口空出来的时间 for(int i=0;i<K;i++) window[i]=opentime;//第一次初始化为开始时间 double wait=0,cnt=0;//用于计算等待的总时间 for(int i=0;i<N;i++){ /*先找出三个窗口空出来最早的那个*/ int mintime=window[0],min=0; for(int j=1;j<K;j++){ if(window[j]<mintime){ mintime=window[j]; min=j; } } if(cus[i].arrive>endtime)//要关门了 break; cnt++; if(window[min]>cus[i].arrive){//人来的早，但是窗口空出来得晚 wait+=(window[min]-cus[i].arrive);//更新等待时间 window[min]+=cus[i].serve;//计算该窗口下次空出来的时间 } else window[min]=cus[i].arrive+cus[i].serve;//人来的晚，窗口空出来的早；不用等 } if(cnt==0) printf("0.0\n"); else printf("%.1f\n",wait/60.0/cnt); return 0; }