• 1014 Waiting in Line

    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.
    • Customeri​ will take Ti​ 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, customer1​ is served at window1​ while customer2​ is served at window2​. Customer3​ will wait in front of window1​ and customer4​ will wait in front of window2​. Customer5​ will wait behind the yellow line.

    At 08:01, customer1​ is done and customer5​ enters the line in front of window1​ since that line seems shorter now. Customer2​ will leave at 08:02, customer4​ at 08:06, customer3​ at 08:07, and finally customer5​ 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:

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

    Sample Output:

    1. 08:07
    2. 08:06
    3. 08:10
    4. 17:00
    5. Sorry

    题目大意

    有N个窗口，每个窗口最多排队M个人。如果所有窗口都排满了，其他人就在黄线外等待，直到有人完成业务办理。某个窗口的队伍不再排满后，黄线外的人才会选择所有窗口排队人数最少当中：编号最小的那个窗口继续排队。

    窗口从8点开始营业，17点不再办理还未处于服务状态的人

    求每个人都是在什么时候结束业务办理的时间，如无办理，输输出Sorry。

    思路

    经典队列思想

    注意点

    所有人，只要选择了在某个窗口排队，就不会再去其他窗口，哪怕其他窗口已经没有人了。

    所有窗口17.00开始不再服务新的用户办理，但还在服务的人，仍然将其业务办理完成。

    C/C++ 

    1. #include
    2. using namespace std;
    3. int findWindow(); // 找到符合要求的窗口
    4. void Clear();     // 当前最早结束的一个窗口
    5. bool endTime;     //  判断所有窗口是否都结束工作
    6. int N,MAXSIZE,K,Q,nowTime=480,result[1001]; // result 结果存储
    7. queueint,int>> window[21]; // 存储每个窗口办理人员的 id + time
    8. int main()
    9. {
    10.     int num,key;
    11.     cin >> N >> MAXSIZE >> K >> Q;
    12.     for(int z=1;z<=K;z++){
    13.         cin >> num;
    14.         if(endTime) continue;
    15.         key = findWindow();
    16.         window[key].push({z,num});
    17.     }
    18.  
    19.     while (!endTime) Clear();
    20.  
    21.     while (Q--){
    22.         cin >> num;
    23.         if(result[num]>0) printf("%02d:%02d\n",result[num]/60,result[num]%60);
    24.         else puts("Sorry");
    25.     }
    26.     return 0;
    27. }
    28. int findWindow(){
    29.     int flag = 999,op=0;
    30.     for(int z=1;z<=N;z++){
    31.         if(window[z].size()size()
    32.             op = z;
    33.             flag = window[z].size();
    34.         }
    35.     }
    36.     if(flag==999 && !endTime){
    37.         Clear();
    38.         return findWindow();
    39.     }
    40.     return op;
    41. }
    42.  
    43. void Clear()
    44. {
    45.     int minTime = 201314;
    46.     for(int z=1;z<=N;z++){
    47.         if(window[z].empty()) continue;
    48.         minTime = min(minTime,window[z].front().second);
    49.     }
    50.  
    51.     if(nowTime+minTime>=1020)  endTime = true;
    52.     if(endTime){
    53.         for(int z=1;z<=N;z++) if(!window[z].empty()){
    54.             result[window[z].front().first] = nowTime+window[z].front().second;
    55.         }
    56.     }else{
    57.         nowTime += minTime;
    58.         for(int z=1;z<=N;z++) if(!window[z].empty()){
    59.             window[z].front().second -= minTime;
    60.             if(window[z].front().second==0){
    61.                 result[window[z].front().first] = nowTime;
    62.                 window[z].pop();
    63.             }
    64.         }
    65.     }
    66. }

  • 相关阅读:
    原码，反码，补码的关系和计算
    计算机系统中虚拟内存概念解疑（1）
    mybatis的工作原理
    学习二十大奋进新征程线上知识答题小程序登录技术点分析与实现
    EaselJS 源码分析系列--第一篇
    第四十二天 哈希
    Flink动态业务规则的实现
    Numpy计算中的@、*、mutiply、dot的区分（含Python代码）
    javascript大作业《web课程设计》用html做一个期末作业网站，梅西足球体育网页，css
    PHP：BinarySearchTree二叉搜索树(附完整源码)
  • 原文地址：https://blog.csdn.net/daybreak_alonely/article/details/127660535