codeforces] #398(Div.2) B. The Queue [模拟]

链接：Codeforces Round #398 (Div. 2) B. The Queue

题意

Vasya 这个人终于成年了。有一天，他想去办个护照（年龄到了就想出去浪）。说做咱就做，他决定明天就去办事处搞点事情。

但是问题就出现了，办证这种事情一看就会有很多人，哪个时候去可以少排一会儿队呢？

Vasya决定将偷懒进行到底，先是弄来了办事处的开门时间 $t_s$ ，关门时间 $t_f$ 和为每个客户服务需要消耗的时间 $e_t$（这里假设每个客户需要的时间相同）。然后他又通过特殊渠道得知了明天会有 $n$ 个客户，以及每个客户来的具体时间 $n_t$

补充：

  1. Vasya和其他客户到达办事处的时间点均为整点。
  2. 当Vasya和其他人同时到达时，Vasya会表现出他的绅士风度，让其他人排在他前面
  3. 工作人员反应很快，一旦有人来就会马上开始工作
  4. 如果给的数据有多个答案，只需给出其中任意一个答案
  5. Vasya在明天必须拿到护照

分析

题意描述应该非常清晰了，但这个题目里面所包含的各种特殊情况在比赛的时候不是那么容易考虑得到。
所有的情况大概有以下几点：

  1. 来的人不是很多或者工作效率很高，在整个工作时间内有那么一个时刻工作人员在玩手机
  2. 办事处还没开门，但早就有围观群众到场了
  3. 虽然来了很多人，但是大家都睡过了头，在关门之后才到
  4. 人满为患，这一天都有很多人没能办成功的

1 和 3 应该是比较简单的，直接找一个空闲的时间作为答案就可以了。相比较而言比较麻烦的是 2 和 4 。
2 和 4 需要在各个客户之间的时间进行比较判断，才能寻得最优解。
当然这四个都不是难的，结合起来更麻烦。

下面就说一下我的思路：

最优解就在 空闲时间 和 某个客户来之前一分钟的那个时间（$n_t-1$） 其中一个。

空闲时间就不解释了。根本不用等啊。
（但是一定要保证到关门之前有充足的时间来办护照哦，即$t+e_t<t_f$）

后面那个的话就是

  1. 把本来可以排最少时间的客户挤掉，代替他的位置。（这样你就必须比他早来）
  2. 尽可能地不在前面的人身上浪费时间。（只要早一分钟来）

然后这个问题就变成了求哪个客户等的时间最短的问题
（分别求出他们离开的时间就行了）
（总共就$10^6$的客户，都遍历一遍也没问题）

代码

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
#include <cstdio>
typedef __int64 LL;
LL nt[100005];
int main()
{
    LL ts,tf,et;
    while(~scanf("%I64d%I64d%I64d",&ts,&tf,&et)){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%I64d",&nt[i]);
        }
        LL t=ts,ans=nt[1]-1;
        LL low=t-nt[1]+1;   //最少消耗的时间
        if(ans+et>tf){
            ans=ts;
            t=tf+1;
        }
        int f=0;    //判断是否有空闲时间
        for(int i=1;i<=n&&t<=tf;i++){
            if(nt[i]>t){
                ans=t;
                f=1;
                break;
            }
            if(i>1){
                LL l=t-nt[i]+1; //当前客户消耗的时间
                if(l<low){
                    ans=nt[i]-1;
                    low=l;
                }
            }
            t+=et;
        }
        if(f)   printf("%I64d\n",ans);
        else if((t<tf)&&((t+et)<=tf))   printf("%I64d\n",t);
        else    printf("%I64d\n",ans);
    }
    return 0;
}

小结

由于这个题目考虑的点比较多且繁琐（在比赛的时候我真的这样觉得！）所以就收录下来了（其实是个水题）
针对模拟类的题目自己不是特别敏感，写一下也加深印象。

如果有更好的方法或者我有什么不足或者有什么值得探讨的东西的话，可以评论或者联系我。

暴力, 模拟
codeforces, 模拟