PAT甲级-1017 Queueing at Bank

题目

题目大意

银行有k个窗口，每个窗口只能服务1个人。如果3个窗口已满，就需要等待。给出n个人到达银行的时间和服务时间，要求计算每个人的平均等待时间。如果某个人的到达时间超过17:00:00，则不被服务，等待时间也不计算在内。如果某个人早于8:00:00到达，那该人要至少等到8:00:00才能被服务。

思路

银行排队问题，根据题意模拟，和1014相似。首先考虑怎么处理字符串形式的时间，这里我将小时，分钟，秒都计算出来，到达时间用秒来表示。一个人有到达时间，服务时间，还要计算等待时间，因此我用结构体来表示，数据结构就用了一个结构体数组。因为要考虑先后顺序，所以肯定要排序。

排序之后先考虑一般情况，一个人的等待时间 = 窗口的最小结束服务时间 - 到达时间（只有前面的某个窗口结束服务，这个人才能开始服务）。再考虑这个人的到达时间晚于窗口结束服务时间的情况，也就是说，他到银行的时候就已经有空位了。那么他的等待时间 = 0，结束服务时间 = 到达时间 + 服务时间。因此需要一个window数组来记录每个窗口的结束服务时间，也就是可以开始服务下一个人的时间。window数组初始化为8点，也即每个窗口开始服务下一个人的时间是8点。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;struct man{int begin;  // 开始时间（单位：秒）int time;  // 服务时间（单位：秒）int wait;  // 等待时间（单位：秒）
};bool cmp(man x, man y){return x.begin < y.begin;
}int main(){int n, k;cin >> n >> k;vector<man> v;vector<int> window(k, 8 * 3600);  // 记录每个窗口服务结束的时间for (int i = 0; i < n; i++){string s0;int begin, time, wait = 0;cin >> s0 >> time;if (s0 <= "17:00:00"){int h = (s0[0] - '0') * 10 + (s0[1] - '0');int m = (s0[3] - '0') * 10 + (s0[4] - '0');int s = (s0[6] - '0') * 10 + (s0[7] - '0');begin = h * 3600 + m * 60 + s;v.push_back({begin, time * 60, wait});}}sort(v.begin(), v.end(), cmp);for (int i = 0; i < (int)v.size(); i++){int mini = 0, mint = INT_MAX;for (int j = 0; j < k; j++){if (mint > window[j]){mint = window[j];mini = j;}}  // 最小结束时间v[i].wait = max(0, window[mini] - v[i].begin);  // 考虑顾客到达时间在结束时间之后window[mini] = max(window[mini], v[i].begin) + v[i].time;  // 考虑顾客到达时间在结束时间之后}double res = 0.0;for (int i = 0; i < (int)v.size(); i++){res += v[i].wait;}res /= (int)v.size() * 60.0;printf("%.1lf\n", res);return 0;
}