Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.
Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 numbers: N (≤10e4) - the total number of customers, and K (≤100) - the number of windows. Then N lines follow, each contains 2 times: HH:MM:SS - the arriving time, and P - the processing time in minutes of a customer. Here HH is in the range [00, 23], MM and SS are both in [00, 59]. It is assumed that no two customers arrives at the same time.
Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00, and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.
Output Specification:
For each test case, print in one line the average waiting time of all the customers, in minutes and accurate up to 1 decimal place.
Sample Input:
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
Sample Output:
8.2题目大意：有n个客户，k个窗口。已知每个客户的到达时间和需要服务的时长，如果有窗口就依次过去，如果没有窗口就等待，求客户的平均等待时长。银行开放时间为8点到17点，在8点之前来的客户需要先等到8点整才能被服务，在17点后来的人不被服务，也不被计数。每个客户的服务时常不超过1小时。
分析：注意题目要求是17点之后来的才不被服务，只要在8点到17到哪之间来了，即便轮到他的时候是17点之后，均能得到服务。
这道题与1014 Waiting in Line很像，也是队列的模拟题。1014题可以看作事件驱动，是进来一个客户，再去处理之前排队的一个客户。但是这道题有些不同，每一位能被服务的客户都可能有等待时间，不需要下一位客户来驱动，即自己的等待时间只与窗口的当前时间有关，所以每一位客户都可以直接计算。
#include<algorithm>
#include <cstdlib>
#include <cstdio>
#include <ctime>
using namespace std;typedef struct people{int time,work,real_time;
}people;bool cmp(people a,people b)
{if(a.time<b.time)return 1;return 0;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint n,k,wait_sum=0,real_cnt=0;scanf("%d%d",&n,&k);people num[n+5];for(int i=0;i<n;++i){int h,m,s,work;scanf("%d:%d:%d%d",&h,&m,&s,&work);int temp=h*3600+m*60+s;//读入的时候把时间全部转化为秒为单位if(temp>17*3600)continue;//如果来的时候过了17点就不计数num[real_cnt].time=temp;num[real_cnt].work=work*60;real_cnt++;}sort(num,num+real_cnt,cmp);//按照来的先后顺序排序people que[k+5];for(int i=0;i<k;++i)que[i].real_time=8*3600;//把每个柜台的初始时间设定为8点00分00秒for(int i=0;i<real_cnt;++i){int index=0,min_time=1000000;for(int j=0;j<k;++j)//找到当前时间最早的窗口{if(que[j].real_time<min_time)index=j,min_time=que[j].real_time;}if(num[i].time>que[index].real_time)//注意客户来的时间可能比窗口的当前时间晚que[index].real_time=num[i].time;//此时要把窗口时间增加到客户时间wait_sum+=max(0,que[index].real_time-num[i].time);que[index].real_time+=num[i].work;}(!real_cnt)?printf("0.0\n"):printf("%.1f\n",wait_sum*1.0/real_cnt/60);#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
