小根堆
代码:
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<sstream>
using namespace std;
const int N=1e4+10;
struct person{
int arrive_time;
int time;
bool operator<(const person& t)const {//重载符号!!!!
return arrive_time<t.arrive_time;
}
}A[N];
int main(){
int m,n;
cin>>m>>n;
int end=3600*17;
for(int i=0;i<m;i++){
string ss;
int time;
cin>>ss>>time;
int h,m,s;
sscanf(ss.c_str(),"%d:%d:%d",&h,&m,&s);
int temp=3600*h+60*m+s;
A[i].arrive_time=temp;
A[i].time=time*60;//统一单位均为秒
//A[i]={temp,time*60};等价
}
priority_queue<int,vector<int>,greater<int> >windows;//!!!!!!
//采用小根堆存储窗口信息(服务结束时间)
for(int i=0;i<n;i++)
windows.push(3600*8);
sort(A,A+m);
int cnt=0;//应该被服务的顾客
int sum=0;//顾客总共的等待时间
for(int i=0;i<m;i++){
int w=windows.top();
windows.pop();//删掉该窗口
if(A[i].arrive_time>17*3600)
break;
int start=max(A[i].arrive_time,w);
sum+=start-A[i].arrive_time;
cnt++;
int t=min(A[i].time,3600);
windows.push(t+start);//重新加入该窗口,因为小根堆内的元素值不能改变!!!!
}
printf("%.1lf",(double)sum/cnt/60);//这里和double(sum/cnt/60)不一样!!!!!
return 0;
}