AcWing 1494. 银行排队
原题链接
中等
作者:
NameLess丶
,
2023-11-18 10:04:57
,
所有人可见
,
阅读 36
#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
int windows[110];
LL total;
PII customers[10010];
int n,k;
int toint(string s)
{
int res = stoi(s.substr(0,2)) * 3600 + stoi(s.substr(3,2)) * 60 + stoi(s.substr(6));
return res;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i = 1;i <= k;i++) windows[i] = 8*3600;
for(int i = 0;i < n;i++)
{
string s;
int a,b;
cin >> s >> b;
a = toint(s);
customers[i] = {a,min(b*60,3600)};
}
sort(customers,customers+n);
int current_customer = 0;
while(current_customer < n)
{
if(customers[current_customer].first > 17*3600) break;
int choice = 0;
for(int i = 1;i <= k;i++)
if(!choice || windows[i] < windows[choice]) choice = i;
int start_time = max(customers[current_customer].first,windows[choice]);
total += (start_time - customers[current_customer].first);
windows[choice] = start_time + customers[current_customer].second;
current_customer++;
}
printf("%.1lf",total/(current_customer*60.0));
}