[数据结构与算法]二刷PAT:advanced1014:Waiting in Line(尝试了一种新的解法)

看奥特曼入迷了，忘了写题解复盘

这个题以及后面会遇到的很多排队等待问题一样，是很麻烦的分析题。

我在2020年月底刚开始接触时，学习了其他前辈遍历时间根据情况分析的方法，感到十分麻烦，这一次我按照其他前辈关于入队操作，按人分析的方法，感觉思路更加清晰(模拟m行n列插入顾客的方式)。

注解见代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n,m, k, q;
struct node
{
    ll poptime, endtime;    //队头顾客服务结束时间, 当前顾客结束后的时刻
    queue<ll> q;
};

int main(void)
{
    cin>>n>>m>>k>>q;    //窗口，线内人数，服务的顾客数，问询数
    vector<ll> time(k + 1);     //顾客服务完的时刻
    vector<bool> sorry(k + 1, false);  //顾客是否等到了服务
    vector<node> window(n + 1);   //窗口
    vector<ll> result(k + 1);   //顾客服务结束时间
    ll index = 1;
    for (ll i = 1; i <= k; ++i) {cin>>time[i];}
    for (ll i = 1; i <= m; ++i)
    {
        for (ll j = 1; j <= n; ++j)
        {
            if (index <= k)  //对于黄线内的若干名顾客
            {
                //需要注意对队头的元素进行特殊处理
                //超出服务时间9*60则sorry
                window[j].q.push(time[index]);  //顾客入队
                if (window[j].endtime >= 540) {sorry[index] = true;}
                //超出下班时间仍然需要更新当前窗口的endtime
                window[j].endtime += time[index];
                if (i == 1) {window[j].poptime = window[j].endtime;}  //队头元素需要更新其出队时间便于黄线外元素入队
                result[index] = window[j].endtime;
                index++;
            }
        }
    }
    while (index <= k)
    {
        //找到队头最快结束的窗口
        ll tmpwindow = 1, tmptime = window[1].poptime;
        for (ll i = 2; i <= n; ++i)
        {
            if (window[i].poptime < tmptime) {tmptime = window[i].poptime; tmpwindow = i;}
        }
        window[tmpwindow].q.pop();
        window[tmpwindow].q.push(time[index]);
        if (window[tmpwindow].endtime >= 540) {sorry[index] = true;}
        window[tmpwindow].endtime += time[index];
        window[tmpwindow].poptime += window[tmpwindow].q.front();  //更新队头的出队时间(服务结束时间)队头后面紧挨着的元素
        result[index] = window[tmpwindow].endtime;
        index++;
    }
    ll id;
    while (q--)
    {
        cin>>id;
        if (sorry[id]) {printf("Sorry\n");}
        else {printf("%02d:%02d\n", (result[id] + 480) / 60, (result[id] + 480) % 60);}
    }
    return 0;
}

睡了睡了