AcWing 1494. 银行排队(pair版)
原题链接
中等
作者:
Hrbust_Lmh
,
2020-04-06 08:51:35
,
所有人可见
,
阅读 817
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int N = 1e4 + 10;
int n, m, hh, mm, ss, service_time;
pair<int, int> persons[N];
priority_queue<int, vector<int>, greater<int> > q;
int main(){
cin >> n >> m;
for(int i = 0; i < n; i ++) {
scanf("%d:%d:%d %d", &hh, &mm, &ss, &service_time);
service_time = min(60, service_time);
persons[i] = make_pair(hh * 3600 + mm * 60 + ss, service_time * 60);
}
sort(persons, persons+n); // pair默认排序是按first排,相同时按second排序
for(int i = 0; i < m; i ++) q.push(8 * 3600); // 把m个窗口的开始时间全部安排好
int sum = 0, cnt = 0;
for(int i = 0; i < n; i ++){
int come = persons[i].first, service = persons[i].second;
int cur_time = q.top(); q.pop(); // 取出堆顶
if(come > 17 * 3600) break;
int start_time = max(come, cur_time);
sum += start_time - come;
q.push(start_time + service);
cnt ++;
}
printf("%.1lf\n", (double)sum / cnt / 60);
return 0;
}