题目描述
假设一家银行有 K 个服务窗口。
窗户前面有一条黄线,将等候区分为两部分。
所有客户都必须在黄线后面排队等候,直到轮到他/她服务并且有可用的窗口为止。
假定一个窗口不能被单个客户占用超过 1 小时,即如果某位顾客的业务已经办理了一小时,则立即终止此项业务。
现在给定每个客户的到达时间 T 和业务办理时间 P,请计算所有客户的平均等待时间。
输入格式
第一行包含两个整数 N 和 K,分别表示客户数量以及窗口数量。
接下来 N 行,每行包含两个时间,分别是一个客户的到达时间,用 HH:MM:SS 表示,以及一个客户的业务办理时间 P(单位:分钟)。
HH 在 [00,23] 范围内,MM 和 SS 都在 [00,59] 范围内。
所有客户的到达时间均不相同。
请注意,银行的营业时间为 08:00 至 17:00。
任何人提前到达都必须排队等候至 08:00,而任何人来得太晚(在 17:00:01 或之后到达)都将不被服务也无需计入平均值。
注意只要客户在17:00之前排上队,则即使办理业务时超过17:00,也会被服务。
输出格式
输出平均等待时间(单位:分钟),结果保留一位小数。
注意,从到达银行至开始办理业务这一期间视为等待期间。
数据范围
1≤N≤104,
1≤K≤100
样例
输入样例:
7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10
输出样例:
8.2
算法1
(暴力枚举) $O(nk)$
和前面做过的以恶搞题目是比较像的
使用一个sum数组来存储每一个窗口需要花费 的时间
q数组存储每一个窗口的当前这个人结束所要花费的时间
全部转换为秒会比较容易计算
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,k;
int q[100+10];
int sum[100+10];
struct lis
{
string time;
int co;
};
bool cmp(lis a,lis b)
{
return a.time<b.time;
}
lis a[N];
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>a[i].time>>a[i].co;
}
sort(a,a+n,cmp);
int cnt=n;
// for(int i=0;i<n;i++)cout<<a[i].time<<" "<<a[i].co<<endl;
for(int i=0;i<n;i++)
{
int hour,minute,second;
int costtime;
string time=a[i].time;
// string t1=time.substr(0,2);
// cout<<time<<endl;
// cout<<(t1);
hour=stoi(time.substr(0,2));
minute=stoi(time.substr(3,2));
second=stoi(time.substr(6,2));
costtime=a[i].co;
// printf("%d %d %d %d \n",hour,minute,second,costtime);
if(costtime>=60)costtime=60;//中止业务
int total_start=hour*3600+minute*60+second;//这个人的开始时间
if(total_start>17*3600)
{
cnt--;
continue;
}
// cout<<total_start<<" ";
// if(total_start<8*3600)total_start=8*3600;
int total_ends=0;
if(total_start<=8*3600)
{
total_ends=8*3600+costtime*60;//这个人的结束时间
}
else
{
total_ends=total_start+costtime*60;
}
int t=-1;
for(int j=0;j<k;j++)
{
if(t==-1||q[j]<=q[t])t=j;
}//找到最快的一个人
if(q[t]<total_start)
{
q[t]=total_ends;
if(total_start<8*3600)sum[t]+=8*3600-total_start;
}
else
{
sum[t]+=q[t]-total_start;
// cout<<q[t]-total_start<<endl;
q[t]=q[t]+costtime*60;
}
// if(q[t]==0)
// {
// q[t]=total_ends;
// // cout<<q[t]<<endl;
// }
// else
// {
// if()
// sum[t]+=q[t]-total_start;//加入等待时间
// q[t]=q[t]+costtime*60;
// // cout<<q[t]<<endl;
// }
}
int sumOfSecond=0;
for(int i=0;i<k;i++)sumOfSecond+=sum[i];
// cout<<sumOfSecond;
printf("%.1lf",sumOfSecond/60.0/cnt);
return 0;
}