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;
}