AcWing 1494. 银行排队
原题链接
中等
作者:
xxxxuu
,
2021-04-20 22:30:26
,
所有人可见
,
阅读 366
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int N=10010,M=110;
struct person{
int arrive_time;//到达时刻
int service_time;//要求在窗口的服务时间
}persons[N];
bool cmp(person a,person b){//按到达时刻排序
return a.arrive_time<b.arrive_time;
}
int main(){
int n,m;//客户数量 窗口数量
cin>>n>>m;
for(int i=0;i<n;i++){
int hour,mintue,second,service_time;
scanf("%02d:%02d:%02d %d",&hour,&mintue,&second,&service_time);
int arrive_time=hour*3600+mintue*60+second;
service_time=min(60,service_time);
persons[i].arrive_time=arrive_time;
persons[i].service_time=service_time*60;
}
sort(persons,persons+n,cmp);//按到达时刻排序
priority_queue<int,vector<int>,greater<int>> windows;
for(int i=0;i<m;i++){//初始化窗口,从08:00:00开始
windows.push(8*3600);
}
int sum=0,count=0;//sum为总等待时间 count统计被服务的人数
for(int i=0;i<n;i++){
auto person=persons[i];
if(person.arrive_time>17*3600){//五点后来的,滚
break;
}
int w=windows.top();//窗口空闲时刻最小值
int start_time=max(person.arrive_time,w);//开始服务的时刻,为到达时刻和窗口空闲时刻的最大值(包含来的时间早于8点情况)
windows.pop();//可用窗口减一
count++;
sum+=start_time-person.arrive_time;//等待时间为 开始服务时刻-到达时刻
windows.push(start_time+person.service_time);//更新下一次窗口空闲的时刻
}
printf("%0.1f",(double)sum/count/60);
return 0;
}