思路
跟1014题很像,也是一道模拟排队题。区别在于1014侧重单入口多出口的排队,默认所有人都在开始时刻开始排队,而1017题黄线前的若干条队伍每队只能容纳1人,并且考虑不同时刻的到达。
数据结构考虑一个结构体Customer代表排队的人,两个成员变量:到达时间、业务办理所需时长。用一个vector<Custmoer>代表队列,sort函数(#include<algorithm>)使其按照到达时间排序即可。还有一个整型数组,下标代表窗口编号,其值代表每个窗口恢复空闲的时刻,最开始为八点,过程中为占用这个窗口的用户的到达时间加上其业务所需时长。
以上是大致思路,还有两个细节需要考虑:
- 17:00及以后到达的,不能加入vector,直接忽略即可。
- 8:00以前到达的,如果把算法写的具有普遍性,那么这一点就完全不需要考虑。我的做法是,定义一个标记变量bool nowait,把客户分成经历了等待时间的,和未经历等待时间的,分别处理,这样算法就可能会简单一些。
代码
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct Customer
{
int atime;
int ptime;
};
vector<Customer> lines;
int windows[100];
bool cmp(Customer a, Customer b)
{
return a.atime < b.atime;
}
int main()
{
int N, K;
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++)
{
int h, m, s, p;
scanf("%d:%d:%d%d", &h, &m, &s, &p);
Customer c;
c.atime = h * 3600 + m * 60 + s;
c.ptime = p;
if (c.atime < 17 * 3600)
{
lines.push_back(c);
}
}
for (int i = 0; i < K; i++)
{
windows[i] = 8 * 3600;
}
sort(lines.begin(), lines.end(), cmp);
float sum = 0;
for (int i = 0; i < lines.size(); i++)
{
bool nowait = false;
int min = 10000000;
int w = -1;
for (int j = 0; j < K; j++)
{
if (windows[j] < lines[i].atime)
{
windows[j] = lines[i].atime + lines[i].ptime * 60;
nowait = true;
break;
}
if (windows[j] < min)
{
min = windows[j];
w = j;
}
}
if (!nowait)
{
sum += windows[w] - lines[i].atime;
windows[w] += lines[i].ptime * 60;
}
}
printf("%.1f", sum / 60.0 / (float)lines.size());
return 0;
}