1017 Queueing at Bank (25 分)

题目传送门：1017 Queueing at Bank (25 分)

一、题目大意

n个人，k个窗口，求平均每个人等待的时间。超过17:00到达的人不会被服务，也就是不算入平均时间。8:00开门，来早的人要等到8:00才会得到服务。

二、解题思路

定义一个结构体存储每个人来到银行的时间、开始被服务的时间、结束被服务的时间。定义一个优先级队列，先把前k个人塞入队列里。剩下的人，每当有人要入队，就必须有人要出队。所以选择结束时间最早的人出队来让后面的人入队。因此自定义的结构体中要实现比较规则小于号，让后结束的人排在前面，优先级队列默认是大顶堆，优先弹出先结束的人。（我就是结构体的比较规则写成了开始时间比较以至于样例一直不过，改过来后果然一遍AC了，思路没问题）

计算公式：等待时间 = 开始服务时间 - 来到银行的时间

注意：没到8:00就来的前k个人也被算入等待时间，要参与平均时间的计算。

小技巧：对时间的加减处理，建议一开始就转化为时间戳来操作，要不然过程中拿着时间字符串来操作太繁琐。

三、AC代码

#include<bits/stdc++.h>
using namespace std;
template<typename T = int>
T read(){
	T x;
	cin >> x;
	return x;
}
struct ZJ{
	int time;// 到达银行的时间
	int len; // 服务的时间长度
	int start, end; // 开始被服务的时间、结束被服务的时间。
	bool operator<(const ZJ&that)const {
		return end > that.end;// 自定义排序规则，为大顶堆优先级队列提供比较规则。
	}
};
int parseInt(string s){// 字符串时间转整数时间戳
	transform(s.begin(), s.end(), s.begin(), [](char c)->char{
		return c == ':' ? ' ' : c;
	});// 将冒号替换成空格，为了用iss流解构整数
	istringstream iss(s);
	int h, m, ss;
	iss >> h >> m >> ss;
	int ret  = h * 3600 + m * 60 + ss;
	return ret;
}
int main(){
	freopen("input.txt", "r", stdin);
	int n = read(), k = read();
	vector<ZJ>V(n);
	for(auto &i: V){
		i.time = parseInt(read<string>());
		i.len = read();
	} 
	sort(V.begin(), V.end(), [](ZJ z1, ZJ z2)->bool{
		return z1.time < z2.time; // 按照达到银行的时间给n个人排序，先来先服务。
	});
	priority_queue<ZJ>Q;
	int t = min(n, k);
	int Eight = 8 * 3600, Fifth = 17 * 3600;
	int sum = 0, total = 0;
	for(int i = 0; i < t; i++){
		if(V[i].time > Fifth)break;
		V[i].start = max(V[i].time, Eight);// 注意开始服务时间的计算
		V[i].end = V[i].start + V[i].len * 60;// 注意结束时间的计算。
		sum += V[i].start - V[i].time; // 等待时间 = 开始服务时间 - 来到银行的时间
		total ++;
		Q.push(V[i]);
	}
	while(t < n){
		ZJ head = Q.top();
		Q.pop();
		if(V[t].time > Fifth)break;
		V[t].start = max(V[t].time, head.end);// 注意开始服务时间的计算
		V[t].end = V[t].start + V[t].len * 60;// 注意结束时间的计算。
		sum += V[t].start - V[t].time; // 等待时间 = 开始服务时间 - 来到银行的时间
		total ++;
		Q.push(V[t]);
		t++;
	}
	cout << fixed << setprecision(1) << sum / 60.0 / total <<endl;// 输出平均等待时间。
} 

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/98441974