【PAT甲级】1014 Waiting in Line (30 分)（队列维护）

题面：

输入四个正整数N,M,K,Q（N<=20,M<=10,K,Q<=1000）,N为银行窗口数量，M为黄线内最大人数，K为需要服务的人数，Q为查询次数。输入K个正整数，分别代表每位顾客需要被服务的时间，Q次查询每次查询一位顾客被服务完离开银行的时间。如果他在五点以前（不包括五点）没有开始被服务，输出“Sorry”。

trick：

在五点以前（不包括五点）没有开始被服务，输出“Sorry”，而不是被服务完时间在五点以后（以题面为准）。

AAAAAccepted code：

 #include<bits/stdc++.h>

 using namespace std;

 int a[];

 queue<pair<int,int> >qu[];

 int ans[];

 int quy[];

 int sum[];

 int main(){

     int n,m,k,q;

     cin>>n>>m>>k>>q;

     for(int i=;i<=k;++i)

         cin>>a[i];

     for(int i=;i<=q;++i)

         cin>>quy[i];

     for(int i=;i<=m;++i)

         for(int j=;j<=n;++j)

             if((i-)*n+j<=k)

                 qu[j].push({a[(i-)*n+j],(i-)*n+j});

     int flag=m*n+;

     while(){

         int mn=1e9;

         for(int i=;i<=n;++i)

             if(!qu[i].empty()&&qu[i].front().first+sum[i]<mn)

                 mn=qu[i].front().first+sum[i];

         if(mn==1e9)

             break;

         for(int i=;i<=n;++i)

             if(!qu[i].empty()&&qu[i].front().first+sum[i]==mn){

                 if(sum[i]>=)

                     ans[qu[i].front().second]=-;

                 else{

                     sum[i]=mn;

                     ans[qu[i].front().second]=sum[i];

                 }

                 qu[i].pop();

                 if(flag<=k){

                     qu[i].push({a[flag],flag});

                     flag++;

                 }

             }

     }

     for(int i=;i<=q;++i){

         int hour=ans[quy[i]]/+;

         int minute=ans[quy[i]]%;

         if(ans[quy[i]]==-)

             cout<<"Sorry";

         else{

             if(hour<)

                 cout<<""<<hour<<":";

             else

                 cout<<hour<<":";

             if(minute<)

                 cout<<""<<minute;

             else

                 cout<<minute;

         }

         cout<<"\n";

     }

     return ;

 }