每日两道算法题 Day13 of PAT---|1014 Waiting in Line (30分)---|跳坑、理思路必看---|队列相关

2022-08-17 22:20:13

1014 Waiting in Line (30分)

Suppose a bank has N windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. The rules for the customers to wait in line are:

The space inside the yellow line in front of each window is enough to contain a line with M customers. Hence when all the N lines are full, all the customers after (and including) the (NM+1)st one will have to wait in a line behind the yellow line.
Each customer will choose the shortest line to wait in when crossing the yellow line. If there are two or more lines with the same length, the customer will always choose the window with the smallest number.
Customer​i​​ will take T​i​​ minutes to have his/her transaction processed.
The first N customers are assumed to be served at 8:00am.
Now given the processing time of each customer, you are supposed to tell the exact time at which a customer has his/her business done.

For example, suppose that a bank has 2 windows and each window may have 2 customers waiting inside the yellow line. There are 5 customers waiting with transactions taking 1, 2, 6, 4 and 3 minutes, respectively. At 08:00 in the morning, customer​1​​ is served at window​1​​ while customer​2​​ is served at window​2​​ . Customer​3​​ will wait in front of window​1​​ and customer​4​​ will wait in front of window​2​​ . Customer​5​​ will wait behind the yellow line.

At 08:01, customer​1​​ is done and customer​5​​ enters the line in front of window​1​​ since that line seems shorter now. Customer​2​​ will leave at 08:02, customer​4​​ at 08:06, customer​3​​ at 08:07, and finally customer​5​​ at 08:10.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 4 positive integers: N (≤20, number of windows), M (≤10, the maximum capacity of each line inside the yellow line), K (≤1000, number of customers), and Q (≤1000, number of customer queries).

The next line contains K positive integers, which are the processing time of the K customers.

The last line contains Q positive integers, which represent the customers who are asking about the time they can have their transactions done. The customers are numbered from 1 to K.

Output Specification:

For each of the Q customers, print in one line the time at which his/her transaction is finished, in the format HH:MM where HH is in [08, 17] and MM is in [00, 59]. Note that since the bank is closed everyday after 17:00, for those customers who cannot be served before 17:00, you must output Sorry instead.

Sample Input:

2 2 7 5
1 2 6 4 3 534 2
3 4 5 6 7

Sample Output:

08:07
08:06
08:10
17:00
Sorry

此题说难也难，说简单也简单，接下来咱们就来捋捋思路，避一避坑

世上本没有坑，只是读题的速度太快了，才被绊了脚
------ said by沃兹基硕得、

题目说了一大套，我来给各位爷总结总结：

银行早八点开业，共有N个窗口，也就是总共N个队伍，当然，队伍长度被一条黄线限制，最长为K，其余人场外候着，依次看哪条队短就去哪条队排队。已知银行晚五点下班，试求顾客被服务结束离店的时间分别是几点几分。

好，这么翻译，已经够简单的了，但，还可以更简单----题目上说线外人排队规则是哪对短就去哪队，难不成我坐那一队一队一个人一个人的算？

不存在的，要以静制动，本来队是满的，按照题意，就只要看哪一队队伍先走人就去哪队，也就是俗话所说的见缝插针

讲道理，这破英文到底没有中文博大精深，太呆板，给大家理解题意也制造了障碍

Attention：

看坑！
  • 最后一句晚五点下班，并不是指顾客离店时间要在五点之前，难不成我四点开始办的业务，因为柜员五点要下班就直接中断了？所以，这题的边界条件是服务开始的时间而不是所求的结束时间

Details:

首先用一个长度为1001的 数组–time[1001] 来存放每个人办业务的时间，后期还可以用作存储离店时间，单位为分钟，前期单纯表示业务时间段长度，后期经过计算表示距离早八点的时间偏移量

然后既然有队伍，那么就需要定义队列，又考虑到有N个队列，那就将队列嵌套在vector中, —>vector< queue < int > > allWindows;

然后再定义一个计时器(vector< int >counter)，记录当前代入队的客户在该队需要等待的时间长度，也就是该队前面客户离店所耗时长 ，也是当前客户业务开始时的时间偏移量，是用作判断是否能在当日接受服务以及计算离店时间的辅助手段

具体的：先将N * K个客户按照顺序摆放好，依次入队，并更新好计时器，然后从N*K+1个客户开始，见缝插针，比较当前队伍哪队对头所剩时间最少，也就是哪队队头最先离开，找到之后标记好，将所有窗口队头时间都减去那个剩余时间最少的时间，以此表示剩余时间最少的客户离队，此时，待入队顾客入队，并更新计时器和自身离店时间

最后只要按照每个人更新过的离店时间偏移量输出离店时间或者Sorry即可（业务开始时就已经下班的直接将离店时间更新为无穷大，方便输出时操作）

Code：

#include <bits/stdc++.h>
using namespace std;
#define Max 0x3f3f3f
int time[1001]={0};////////////////////////////////先用来存放个人用时，计算后用来存放结束时间 
int numWin, numLine, numCus, numQCus;//////////////分别表示：窗口数，线内长度，顾客数量，要求查询的顾客数量 
vector<queue<int> > allWindows(numWin+1);//////////用来存放每个窗口线内队伍的每个人的服务时间 
vector<int> counter(numWin+1);/////////////////////用来存放当前每队确定要消耗的时间 
void OutTime(int offTime){/////////////////////////输出结束时间 
   if(offTime==Max)
      cout<<"Sorry";
   else{
        int h =8+offTime/60;
        int s=offTime%60;
        printf("%02d:%02d", h, s);
   }
}
int main(){
   scanf("%d %d %d %d", &numWin, &numLine, &numCus, &numQCus);
   for(int i=1;i<=numCus;i++)
      scanf("%d", &time[i]);
   fill(counter.begin(),counter.end()+1,0);////////初始化计时器 
   ////////////////////////////////////////////////先按顺序放置线内队列 
   for(int i=1;i<=numWin*numLine;i++){
      allWindows[(i-1)%numWin+1].push(time[i]);////直接入各自窗口的队 
      if(counter[(i-1)%numWin+1]>=540){////////////如果该队计时器已经超时（服务开始时已经下班） 
          time[i]=Max;   				///////////就将此人的结束时间设为无穷大
          continue;
      }
      time[i]+=counter[(i-1)%numWin+1];///////////不超时，那就将结束时间更新为该队计时器时间（服务开始时间）加上服务预计消耗时间 
      counter[(i-1)%numWin+1]=time[i];////////////更新计时器 
   }
   for(int i=numWin*numLine+1;i<=numCus;i++){/////开始逐个放置线外顾客 
      int flag, min;
      flag=min=Max;
      for(int j=1;j<=numWin;j++)//////////////////先寻找每队对头中谁最小 
         if(allWindows[j].front()<min){///////////     （意味着，哪个队伍人数先减一） 
            min=allWindows[j].front();
            flag=j;///////////////////////////////做上标记 
         }
      if(counter[flag]>=540){/////////////////////如果该队计时器，也就是当前待入队顾客的等待时间超过营业时间 
         time[i]=Max;   //////////////////////////就将此人的结束时间设为无穷大，过一会直接输出Sorry 
         continue;
      }
      allWindows[flag].push(time[i]);/////////////时间来得及那就入队 
      for(int j=0;j<flag;j++)/////////////////////入队代表之前那个人服务时间已满 
         allWindows[j].front()-=allWindows[flag].front();
      for(int j=flag+1;j<=numWin;j++)/////////////相应的，其他队队头的剩余时间应该减去这段时间  
         allWindows[j].front()-=allWindows[flag].front();
      allWindows[flag].pop();/////////////////////此人离开 
      time[i]+=counter[flag];/////////////////////获得入队顾客预计离店时间 
      counter[flag]=time[i];//////////////////////更新该队计时器 
   }
   for(int i=0;i<numQCus;i++){
      int temp;
      scanf("%d", &temp);/////////////////////////读取序号 
      OutTime(time[temp]);////////////////////////根据序号输出离店时间 
      if(i<numQCus-1)   cout<<endl;
   }
   return 0;
}

Summary and harvest

(for my current level)

queues are a type of container adaptor, specifically designed to operate in a FIFO context (first-in first-out), where elements are inserted into one end of the container and extracted from the other.

Elements are pushed into the “back” of the specific container and popped from its “front”.

shall support at least the following operations:

  • empty
  • size
  • front
  • back
  • push_back
  • pop_front
上一篇：RL | | UAV


下一篇：LeetCode力扣刷题数据库（183）：从不订购的客户