NOIP模拟 2017/3/12

发表于 | 分类于

NOIP 模拟赛

Author：HJWJBSR&duyege

Blue

Blue 是个动物学家，不仅喜欢研究猫和老鼠，还喜欢研究青蛙。

他最近开始研究青蛙过河的问题，可以简化成：数轴上$ 0 $为岸边，$L $为河对岸。$(0,L)$中间存在 n 个石子。已知青蛙一跳可以跳距离$ D$，而且不能沾水。求问能不能跳到河对岸。当然他觉得这个问题非常 naïve，于是在思考如果青蛙有 $m$ 个，且石头被踩过之后就会沉下去，$m $个青蛙还能不能依次安全过河。如果不能则问最多能有多少个过河。

输入

第一行为一个正整数$ T $代表数据组数。每组数据第一行四个正整数：$n、m、D、L$。第二行 n 个升序正整数 $ai $代表第 $i $个石子坐标为 $ai$。保证没有重复且都小于$ L$。

输出

$T$行”Excited”代表全部能过河或者一个整数代表有多少个能过河的。

对于 10%的数据保证 m=1.
对于另外 10%的数据保证 D=L.
对于另外 10%的数据保证 n=L-1.
对于另外 30%的数据保证 n<=100, L<=10^5.
对于 100%的数据保证 m<=n<=10^6,D<=L<=10^9.
数据范围中的 n、m 皆代表题目描述中 n、m 的总和。

SAMPLE

INPUT

5
10 9 16 30
2 4 6 9 11 15 18 19 25 27 
10 1 23 30
10 11 13 14 15 16 18 26 27 29 
10 7 28 30
2 3 7 9 12 15 20 24 27 28 
10 3 18 30
1 6 9 14 18 19 22 27 28 29 
10 7 10 30
1 2 4 6 18 19 20 22 23 26

OUTPUT

5
Excited
Excited
Excited
0

既然作为第一题，绝对不会是DP，通常就是简单的贪心了。

考试时想的比较多，由于需要求出人数，考虑到转化为二分判断可行性。判断还是用贪心，依次往后跳，记录下来最后看看有没有超过$D$的，复杂度$O(nlogn)$。

然而正解是$O(n)$的直接贪心，对于每次跳，在每次跳的过程中，能跳过去最少的一次人数就是能跳过去的人数。

题解的代码变量名十分惊奇，我就发一下自己的代码好了。

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N =1e6+1;
int t,n,m,d,l,a[N],b[N];
bool can(int ans)
{
    memset(b,0,sizeof(b));
    int anss=0;
    for(int now=1;now<=n;++now)
    {
        if(a[now]-b[++anss]<=d)b[anss]=a[now];
        if(anss==ans)anss=0;
    }
    for(int i=1;i<=ans;++i)
        if(l-b[i]>d)
            return 0;
    return 1;
}
int main()
{
    freopen("Blue.in","r",stdin);
    freopen("Blue.out","w",stdout);
    scanf("%d",t);
    while(t)
    {
        scanf("%d%d%d%d",&n,&m,&l,&d);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        int ll=0,rr=m,mid;
        while(ll!=rr)
        {
            mid=ll+rr+1>>1;
            if(can(mid))	
                ll=mid;
            else			
                rr=mid-1;
        }
        if(rr==m)
            printf("Excited\n");
        else 
            printf("%d\n",rr);
    }
    return 0;
}