1014 Waiting in Line (30 分)

一、题目大意

题目传送门：1014 Waiting in Line (30 分)
银行有n个窗口，每个窗口前面最多可排m个人，共有k个人来银行办理业务，已知了每个人办理业务需要花费的时间。求指定的q个人什么时刻可以办完业务。银行在8:00上班，在17：00之后下班，如果处理到某人已经下班了则输出Sorry。每个窗口排满了m个人后，剩下的人要等候有人办完业务后才能排入窗口前的队伍，优先选择窗口人少的排，如果有多个窗口人数相同，则选择编号小的。

二、解题思路

本题使用的数据结构是vector<list<int>>D,也就是把每个窗口的队伍都看成是一个list链表。用vector<int>leave存储每个人办完业务离开时的时间。

1. 如果k<=n*m的话，那么所有人都可以全部排好。那么所有人办理业务的结束时间可以直接算出来。前n个人直接排在每个窗口的最前面，他们办完业务后离开时的时间就是他们办业务所需时间（因为他们是第一波嘛）。后面的人离开时间为他们前面人的离开时间加上这个人办理业务所花时间。

2. 如果k>n*m的话，我们可以先将前n*m个人先排好，如1所示，然后循环遍历每个链表的头，看表头中哪个人离开时间最早，就将剩下的人中入队一个到这个队中，离开时间同1计算方式。然后这个队头出队。

3. 注意点：这道题中虽说17:00下班，但是如果某个人在17:00之前被服务，那么会等到这个人被服务完才下班。而如果这个人还没服务到他就已经是超过17:00了则不被服务，输出Sorry。这个点我刚开始没想到，以至于只过了一半数据。我将超过17:00被服务的人的leave设置为INT_MAX，最后判断如果这个人的leave值为INT_MAX则输出Sorry，这里改过来后就AC了。

三、AC代码

#include <bits/stdc++.h>
using namespace std;
template<typename T = int>
T read(){
    T x;
    cin >> x;
    return x;
}
template <typename T = int>
void OO(vector<T>v, string s=""){
    cerr<<s <<":"<< endl;
    for(auto i: v){
        cerr << i << ' ';
    }
    cerr << endl;
}
typedef unsigned long long ll;
int main(){
    freopen("input.txt", "r", stdin);
    int n = read(), m = read(), k = read(), q = read();
    vector<int>v(k);//所需时长
    for(int i = 0; i < k; i++){
        v[i] = read();
    }
    vector<list<int>>D(n);//模拟窗口
    vector<int>leave(k, INT_MAX);//离开的时间
    int t = min(n*m, k);
    for(int i = 0; i < t; i++){
        auto p = D.begin();
        for(auto j = D.begin()+1; j != D.end(); j++){
            if((*j).size() < m and (*j).size() < (*p).size()) p = j;
        }//寻找最短的队伍。其实有点多余。刚开始是按顺序排的
        if((*p).size() <= 0){
            leave[i] = v[i];//这是每个窗口第一个人离开的时间
        }else{
            if(leave[(*p).back()] < 540){//540就是17:00
                leave[i] = v[i] + leave[(*p).back()];//这是非第一个人，被服务到的，离开的时间
            }else{//他前面的一个人离开时已经超过了17:00了，那这个人将无法得到服务
                leave[i] = INT_MAX;
            }
        }
        (*p).push_back(i);//排入队中
    }
    while(t < k){//t为剩下的人，循环插入t
        auto p = D.begin();
        for(auto j = D.begin()+1; j != D.end(); j++){
            if(leave[(*j).front()] < leave[(*p).front()]) p = j;
        }//找到n个窗口中哪个窗口的人先出队
        if(leave[(*p).back()] < 540){//计算规则同上
            leave[t] = v[t] + leave[(*p).back()];
        }else{
            leave[t] = INT_MAX;
        }
        (*p).push_back(t);//t入队
        (*p).pop_front();//队头出队
        t++;
    }
    for(int i = 0; i < q; i++){
        int r = leave[read()-1];
        if(r >= INT_MAX){
            cout << "Sorry" << endl;//已经服务开始时间超过了，得不到服务
        }else{
            cout << setw(2) << setfill('0') << r/60+8 << ":" << setw(2) << setfill('0') << r % 60 << endl;//转化为HH:MM格式输出。
        }
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/97694440