1017 Queueing at Bank (25 分)c++实现

题目:

题目链接:https://pintia.cn/problem-sets/994805342720868352/problems/994805491530579968

思路:

思路简单, 对客户列表, 按到的顺序,找到可服务时间最小的窗口办业务

坑点:

  1. 测试点5的的关键, 这道题和之前那个不一样!!如果客户17点前到了,即使轮到他最早也过了17点, 他还是会被服务。
  2. 时间的表示上,很多时候可以用秒来, 可以简化代码。

代码

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
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int BEGIN_TIME = 8 * 60 * 60;
const int CLOSE_TIME = 17 * 60 * 60;
struct customer {
int time, process;
};

bool cmp_time(const customer &c1, const customer &c2)
{
return c1.time < c2.time;
}

int find_window(vector<int> win);

int main()
{
int N, K;
cin >> N >> K;
vector<customer> customer_list;
vector<int> windows(K, BEGIN_TIME);// time when window[index] can serve next people.
while (N--) {
customer c;
int hour, minute, second, pro_time;
scanf("%d:%d:%d %d", &hour, &minute, &second, &pro_time);
c.time = hour * 3600 + minute * 60 + second; // transform time to seconds
if (c.time > CLOSE_TIME) continue;
// if (pro_time > 60) pro_time = 60;
c.process = pro_time * 60;
customer_list.push_back(c);
}
sort(customer_list.begin(), customer_list.end(), cmp_time);
double waiting_time = 0.0;
int served_cnt = 0;
for (auto p : customer_list)
{
int index = find_window(windows);
// if (windows[index] > CLOSE_TIME) break;
if (windows[index] > p.time) {
waiting_time += windows[index] - p.time;
windows[index] += p.process;
}
else {
windows[index] = p.time + p.process;
}
served_cnt++;
}
if (served_cnt)
printf("%.1f", double(waiting_time) / served_cnt / 60);
else printf("0.0");
getchar();
getchar();
return 0;
}

int find_window(vector<int> win)
{
int best_index = 0;
int earliest_time = win[0];
for (int i = 1; i < (int)win.size(); i++)
{
if (win[i] < earliest_time)
{
best_index = i;
earliest_time = win[i];
}
}
return best_index;
}

`