题目描述
$Blue$是个动物学家，不仅喜欢研究猫和老鼠，还喜欢研究青蛙。
他最近开始研究青蛙过河的问题，可以简化成：数轴上$0$为岸边，$L$为河对岸。$(0,L)$中间存在$n$个石子。已知青蛙一跳可以跳距离$D$，而且不能沾水。求问能不能跳到河对岸。当然他觉得这个问题非常$naïve$，于是在思考如果青蛙有$m$个，且石头被踩过之后就会沉下去，$m$个青蛙还能不能依次安全过河。如果不能则问最多能有多少个过河。
输入格式
输入第一行为一个正整数$T$代表数据组数。每组数据第一行四个正整数：$n$、$m$、$D$、$L$。
第二行$n$个升序正整数$a_i$代表第$i$个石子坐标为$a_i$。保证没有重复且都小于$L$。
输出格式
输出$T$行$"Excited"$代表全部能过河或者一个整数代表有多少个能过河的。
样例
样例输入：
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
样例输出：
5
Excited
Excited
Excited
0
数据范围与提示
对于$10%$的数据保证$m=1$。
对于另外$10%$的数据保证$D=L$。
对于另外$10%$的数据保证$n=L-1$。
对于另外$30%$的数据保证$nleqslant 100,Lleqslant {10}^5$。
对于$100%$的数据保证$mleqslant nleqslant {10}^6,Dleqslant Lleqslant {10}^9$。
数据范围中的$n$、$m$皆代表题目描述中$n$、$m$的总和。
题解
一开始我想的是二分答案，但是发现不好搞，于是就想贪心啦。
我们可以设两个指针，让所有的青蛙都在这个范围内，然后跳这个区间，最大化这个区间即可，不用管青蛙的数量是否大于了总数，最后比较就好了。
没什么好说的，一定要记住$"Excited"$怎么拼（考场上拼错疯跑80分）。
时间复杂度：$Theta(n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
#include<bits/stdc++.h>
using namespace std;
int n,m,D,L;
int a[2000000];
int lft,rht;
int ans;
void pre_work()
{
ans=0;
lft=1;
rht=n;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d%d",&n,&m,&D,&L);
pre_work();
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)if(a[i]>D){rht=i-1;break;}
while(lft<=rht)
{
if(a[rht]+D>=L){ans=1;break;}
if(rht==n)break;
if(a[rht+1]-a[lft]<=D)rht++;
lft++;
}
if(!ans){puts("0");continue;}
int flag=rht-1;
while(lft<=flag)
{
if(rht==n)break;
if(a[rht+1]-a[lft]>D)lft++;
else
{
lft++;
rht++;
ans++;
}
}
while(flag>=lft&&a[flag]>=L-D)
{
flag--;
ans++;
}
ans>=m?puts("Excited"):printf("%d
",ans);
}
return 0;
}
rp++