题目

解题思路

本题是一个经典的银行窗口排队问题，还是很有实际意义的。首先读完题，发现题目要求我们给出每个客户的业务结束时间，那么首先来处理存储结构和存储内容：

• 银行的窗口肯定需要一个数组，我们用vector，原因是这个窗口包含的信息很多，我们需要创建一个结构体,包含start_time和end_time，以及一个队列q。两个时间变量表示当前银行窗口的开始服务时间和结束服务时间。队列q存放当前窗口服务客户的编号，比如说1号窗口的q有1，2，4号客户；2号窗口的q有3，5，6号客户。这三个东西是一个窗口所要包含的。
• 然后每个客户有一个办业务的持续时间和结束时间，同时结束时间也是题目要求输出的。我们使用time数组来存放每个客户的持续时间，用time_out数组来存放这个客户几点结束业务。这个time_out也就是最后用来输出题目要求的数组，所以每个过程处理的信息最终都要汇总到这个数组。
• 然后是一个sorry数组，如果有客户的时间时间超出了银行的关门时间，比如1号窗口17：30才能结束，那么后面的人就不能去1号窗口办理业务了，即输出sorry
• 最后老规矩，时间嘛，我们都换算成整数，这个地方没有秒，那就少一个秒，单位是分钟就可以了

那么处理完后，我们来确定代码的一个思路：

• 首先用time数组存储每个客户的业务需求时间
• 然后我们处理黄线内的客户，黄线内的客户是按轮询处理，没有优先级，不会说哪个队伍少就去哪个队，是按顺序来的，这是一个坑点，题目的原话是（ Each customer will choose the shortest line to wait in when crossing the yellow line. ），也就是说你在黄线外的人才需要考虑队伍的长短，黄线内的人是不需要考虑的，按轮询来就行，比如：2个窗口，黄线内容纳2人/每个窗口，那么前1，2，3，4号客户就按轮询的方式排队即可。4号以后的客户在按照队伍长短选择队伍。
• 黄线后的客户，我们需要知道当前哪个队伍最短，那怎么表示队伍最短呢？其实每个窗口的start_time就是用来表示队伍最短的，因为start_time越小，那么说明这个窗口可以越早的办理业务，不就是等同于队伍最短么，同时还解决了权重的问题，即如果两个窗口的start_time一样，我们需要选窗口编号小的那个。
• 最后通过sorry数组和time_out数组输出结果

实现代码

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#include<sstream>
#include<algorithm>
using namespace std;

typedef struct Node
{
    //这里要理解哦，这两个时间的具体作用，前者是为了确定当前窗口啥时候可以服务下一个客户
    //后者是计算当前客户的服务结束后的时间，其实就是题目要求输出的客户结束业务的时间
    int start_time=480,end_time=480;

    //这个队列其实能存放的客户编号永远不能超过M，只能<=M
    //因为黄线内一个队伍只能由M人，而q表示当前窗口黄线内的人的编号
    //如果一个窗口的黄线内有2人，那么第三个人想要来这个窗口办理业务，那么第一个人一定要先出队，第三个才能入队
    queue<int> q;
}NODE;

int main()
{
#ifdef ONLINE_JUDGE                
#else    
    freopen("1.txt", "r", stdin);
#endif 

    int N,M,K,Q;
    cin>>N>>M>>K>>Q;

    //这个地方要写k+1，因为人物编号从1开始，没有0号的
    vector<int> time(K+1),time_out(K+1);
    vector<bool> sorry(K+1,false);

    //人物编号从1开始，而循环变量作为数组下标，所以i=1开始
    for(int i=1;i<=K;i++)
    {
        cin>>time[i];
    }

    //这是窗口数组
    vector<NODE> window(K+1);
    int index=1;            //index是指当前人物编号，从1号开始处理

    //这个双循环表示处理黄线内的人，只要轮询即可
    //外循环是黄线人数/队
    for(int i=1;i<=M;i++)
    {
        //内循环是窗口
        for(int j=1;j<=N;++j)
        {   
            //先判断index时候超过了给定的K
            if(index<=K)
            {
                //当前客户入队，即挑选窗口，窗口的队列q登记信息
                window[j].q.push(index);

                //确保当前窗口没有下班，只要在17：00分以前空闲，都可以服务客户，即便当前窗口的end_time=16：59分
                //否则就是sorry，窗口下班
                if(window[j].end_time>=1020)
                    sorry[index]=true;

                //窗口更新end_time，即当前客户结束的时间
                window[j].end_time += time[index];

                //更新窗口的start_time，方便黄线后面的人找较短的队伍，以便排队
                //这个地方为啥不能是+=time[index]，看着好像也对啊
                window[j].start_time += window[j].end_time;       

                //为啥不能用window[j].starttime+time[index]
                time_out[index]=window[j].end_time;                 

                index++;
            }
        }
    }

    //处理黄线外的，首先就是要找出队伍短的那个
    while(index <= K)
    {
        //用两个变量记录第一个窗口的start_time和窗口编号
        //这样的好处是可以找到最短的队伍，同时如果用多个相同长度的队伍，优先最小的窗口号
        int temp_start_time_min=window[1].start_time,temp_min_window_num=1;
        for(int j=2;j<=N;++j)
        {
            if(temp_start_time_min > window[j].start_time)
            {
                temp_start_time_min=window[j].start_time;
                temp_min_window_num=j;
            }
        }

        //找到了最短队伍所在的窗口，把窗口的队列的队首弹出，让后一个人进来
        window[temp_min_window_num].q.pop();
        window[temp_min_window_num].q.push(index);

        if(window[temp_min_window_num].end_time >= 1020)
            sorry[index]=true;
        else
        {   
            //依次更新end_time,start_time,以及time_out
            //比较上面的start_time更新，这里就是用temp数组进行更新，为啥这里可以，上面不行呢
            window[temp_min_window_num].end_time += time[index];
            window[temp_min_window_num].start_time += time[window[temp_min_window_num].q.front()];
            time_out[index] = window[temp_min_window_num].end_time;
        }
        //time_out[index]=window[temp_min_window_num].end_time;

        index++;
    }

    for(int i=1;i<=Q;++i)
    {
        int temp;
        cin>>temp;
        if(sorry[temp]==true)
            cout<<"Sorry"<<endl;
        else
        {
            printf("%02d:%02d\n",time_out[temp]/60,time_out[temp]%60);
        }
    }

    return 0;
}