有n个客户和k个窗口，给出n个客户的到达时间和需要的时长
有空闲的窗口就去办理，没有的话就需要等待，求客户的平均时长。
如果在8点前来的，就需要等到8点。
如果17点以后来的，则不会被服务，无需考虑。
按客户的到达时间排序
建立一个优先级队列，一开始放入k个窗口，初始结束时间为8*3600
然后for循环客户，每次从优先级队列中取出最早结束时间的窗口
如果客户比结束时间来的早，就需要等待
如果客户比结束时间来的晚，就无需等待
最后只要统计那些到达时间在17*3600之前的客户即可。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
const int maxn=;
int n,k;
struct Customer{
int arrive; //到达时间
int process; //服务时间
int start; //客户开始被服务的时间
int finish; //客户的结束时间
int wait; //客户的等待时间
bool operator<(const Customer tmp)const{
return arrive<tmp.arrive;
} }cus[maxn];
struct Window{
int finish_time;
bool operator<(const Window tmp)const{
return finish_time>tmp.finish_time;
}
};
int main()
{
int h,m,s,t;
scanf("%d %d",&n,&k);
for(int i=;i<n;i++){
scanf("%d:%d:%d %d",&h,&m,&s,&t);
cus[i].arrive=h*+m*+s;
if(t>)
t=; //样例中其实也没有超过60分钟的数据，题目说了是假设
cus[i].process=t*;
}
priority_queue<Window>q;
Window w;
for(int i=;i<k;i++){
w.finish_time=*;
q.push(w);
}
sort(cus,cus+n);
Window ww;
for(int i=;i<n;i++){
w=q.top();
q.pop();
if(cus[i].arrive<w.finish_time){
cus[i].wait=w.finish_time-cus[i].arrive;
cus[i].start=w.finish_time;
cus[i].finish=cus[i].start+cus[i].process;
ww.finish_time=cus[i].finish;
q.push(ww);
}
else{
cus[i].start=cus[i].arrive;
cus[i].wait=;
cus[i].finish=cus[i].start+cus[i].process;
ww.finish_time=cus[i].finish;
q.push(ww);
}
}
double sum=;
int cnt=;
for(int i=;i<n;i++){
/*
一开始和P1014搞混了，以为如果是17点之前还没被服务，就不考虑
后来发现题目中明确说了，是17点之后到的才不考虑
*/
if(cus[i].arrive<=*){
sum+=cus[i].wait;
cnt++;
}
}
if(cnt==)
printf("0.0\n"); //去掉这个也能AC，说明样例没有出现cnt为0的情况
else{
double minutes=sum/60.0/cnt;
printf("%.1lf\n",minutes);
} return ;
}