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