Home PAT 1014 Waiting in Line
Post
Cancel

PAT 1014 Waiting in Line

Link

开始时写成这样是不对的:

1
2
3
4
5
6
7
8
9
10
11
for(;i<=k;++i){
    node top=q.top();
    if(top.tot>=END_TIME) break;
    q.pop();
    //...
}
while(b--){
    //...
    if(ans[a]==-1) printf("Sorry\n");
    //...
}

测试点 4 一直过不了. 后来决定不 break 了, 改成这样就 AC 了:

1
2
3
4
5
6
7
8
9
10
11
for(;i<=k;++i){
    node top=q.top();
    //if(top.tot>=END_TIME) break;
    q.pop();
    //...
}
while(b--){
    //...
    if(ans[a]-p[a]>=END_TIME) printf("Sorry\n");
    //...
}

这是为什么啊? 按理来说我的 tot 记录的就是当前顾客的开始时间啊, 而且这个 tot 还是最小的, 这样 break 有什么不对?

先留个坑. 后面再看.

顺手贴一下我的 AC 代码, 是用优先队列做的. 对于黄线以内的 m 行先单独处理, 放到一个普通队列 oq 中, 等到黄线排满了再将它们放到优先队列 q 中.

当然也可以不用优先队列, 因为每次只需要找到最小的 node, 而不用排序. 但是我第一想法就是用优先队列. 如果不用的话, 那么就用数组维护每个窗口的信息, 包括窗口最快能够结束的时间 (对应我的代码中 node 结构体里的 time) 以及在这个窗口排队能够办理业务的开始时间 (对应 node 结构体里的 tot). 至于排队的有哪些顾客, 也是要按顺序记录的, 可以用普通队列, 也可以用数组加指针.

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
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
const int START_TIME=8*60,END_TIME=17*60;
int n,m,k,b,a;
int p[1010],ans[1010];
struct node{
    int id,time,tot;
    queue<int>cq;
    bool operator<(const node& x)const{
        if(time!=x.time) return time>x.time;
        return id>x.id;
    }
};
priority_queue<node>q;
queue<node>oq;
int main() {
    memset(ans,-1,sizeof(ans));
    scanf("%d%d%d%d",&n,&m,&k,&b);
    int i;
    for(i=1;i<=k;++i)
        scanf("%d",&p[i]);
    i=1;
    for(int j1=1;j1<=m;++j1){
        for(int j2=1;j2<=n;++j2){
            if(i>k) break;
            if(j1==1){
                node temp;
                temp.id=j2,temp.time=temp.tot=START_TIME+p[i];
                oq.push(temp);
                ans[i]=START_TIME+p[i];
            }else{
                node top=oq.front();
                oq.pop();
                top.tot+=p[i];
                ans[i]=top.tot;
                top.cq.push(i);
                oq.push(top);
            }
            i++;
        }
    }
    if(i<=k){
        while(!oq.empty()){
            q.push(oq.front());
            oq.pop();
        }
    }
    for(;i<=k;++i){
        node top=q.top();
        q.pop();
        top.tot+=p[i];
        ans[i]=top.tot;
        top.time+=p[top.cq.front()];
        top.cq.pop();
        top.cq.push(i);
        q.push(top);
    }
    while(b--){
        scanf("%d",&a);
        if(ans[a]-p[a]>=END_TIME) printf("Sorry\n");
        else printf("%02d:%02d\n", ans[a]/60,ans[a]%60);
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.