A1017 Queueing at Bank
摘要
Title: A1017 Queueing at Bank
Tag: 模拟
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
A1017 Queueing at Bank
-
题意
Suppose a bank has K windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line, until it is his/her turn to be served and there is a window available. It is assumed that no window can be occupied by a single customer for more than 1 hour.
Now given the arriving time T and the processing time P of each customer, you are supposed to tell the average waiting time of all the customers. -
思路
先按照来的时间进行排序（不能输入时进行统一到8点，还是要先来后到），结构体排序，之后将完成的时间放入小根堆，每次弹出时间最小的
-
代码
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110/*
* @Author: NEFU AB-IN
* @Date: 2023-01-04 11:58:48
* @FilePath: \GPLT\A1017\A1017.cpp
* @LastEditTime: 2023-01-04 18:48:36
*/
using namespace std;
struct sa
{
int time;
int ptime;
int wtime;
};
int main()
{
int n, k;
cin >> n >> k;
vector<sa> a(n);
int b = 8 * 60 * 60;
int e = 17 * 60 * 60;
for (int i = 0; i < n; ++i)
{
int hh, mm, ss;
scanf("%d:%d:%d %d", &hh, &mm, &ss, &a[i].ptime);
a[i].ptime = min(a[i].ptime, 60);
a[i].ptime *= 60;
a[i].time = hh * 60 * 60 + mm * 60 + ss;
}
auto cmp = [&](const sa a, const sa b) {
if (a.time != b.time)
return a.time < b.time;
else
return a.ptime < b.ptime;
};
sort(a.begin(), a.end(), cmp);
priority_queue<int, vector<int>, greater<int>> q; // 存放结束时间
for (int i = 0; i < k; i++)
q.push(b); // 先把m个窗口安排好
double res = 0;
int cnt = 0;
for (auto &[t, p, w] : a)
{
if (t > e)
break;
int t1 = q.top();
q.pop();
if (t1 > t)
w += (t1 - t);
q.push(max(t1, t) + p);
res += w;
cnt++;
// cout << t << " ";
// cout << w << '\n';
}
printf("%.1lf", res / cnt / 60.0);
return 0;
}
/*
22409 6391
22667 6133
23444 5356
24069 4731
24431 4369
26412 5868
26423 5977
26663 5737
26737 5663
26988 5412
27483 5637
28001 5419
28048 5552
28961 5659
29994 5646
31514 4366
33954 2046
36166 14
38463 0
40097 0
41169 0
41615 0
42574 0
42985 0
43421 0
45192 0
46014 0
46587 0
46957 0
48266 0
49420 0
50181 0
51572 0
52755 0
54059 0
54066 0
54161 0
54470 0
54705 810
55895 0
58852 0
59656 0
59827 0
35.2
*/