题目描述

blablabla

样例

blablabla

算法1

(模拟)

从第0分钟开始模拟每个顾客所做的事情并进行记录。

时间复杂度 $ O(nkc) $

C++ 代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

const int N=1e5;//PAT的数据范围比ACwing的大（随便开的）

int n,m,k,q;
int time1[N];//每个顾客所用的时间
int end1[N];//每个窗口时间总和
int end2[N];//那个人在哪个窗口排队
int long1[N];//每个窗口前的人数
int man[N];//每个人 等待+办理 的时间总和
int st[N];//该顾客是否办理完
int begin1[N];//顾客开始时间

int main()
{
    cin>>n>>m>>k>>q;

    for(int i=1;i<=k;i++) cin>>time1[i];

    long1[0]=0x3f;//设一个初始值

       int cut=0;

       while(cut<540)//这里是从8点->17点总时间（分钟）
       {

       for(int i=1;i<=k;i++) 
       if(cut==man[i]&&man[i]) {long1[end2[i]]--;}//如果当前时间等于顾客办理完成的时间，则顾客离队

       for(int j=1;j<=k;j++)//枚举每位顾客
       {
        if(!st[j])
        {
        int min=0;//当前最小人数的窗口编号
        for(int i=1;i<=n;i++)
          if(long1[i]<long1[min]) min=i;//保证编号最小，所以不能等于

         if(long1[min]<m) {
             long1[min]++;//队伍人数增加
             begin1[j]=end1[min];//每个顾客从什么时候开始排队
             end1[min]+=time1[j];
             end2[j]=min;//j顾客在min队列排队
             man[j]=end1[min];//第j个顾客的结束时间
             st[j]=1;//顾客办理过则不能再次枚举
         }else break;//如果最短队列满了(说明所有队伍都满了)，就break；
        }
       }

       cut++;//分钟+1
       }

       while(q--)
       {
           int x;cin>>x;
           int s=8;int f=0;
           s+=man[x]/60;//时钟
           f+=man[x]%60;//分钟
           if((!man[x])||begin1[x]>=540)//对于开始时间大于540分钟的或者没有开始办理就结束的顾客
           {
               cout<<"Sorry"<<'\n';
               continue;
           }
           if(s<10) printf("0");
           printf("%d:",s);
           if(f<10) printf("0");
           printf("%d\n",f);
       }



    return 0;
}

blablabla