[CSP-S模拟测试]:Blue（贪心）

题目描述

_{$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%$的数据保证$n\leqslant 100,L\leqslant {10}^5$。
对于$100%$的数据保证$m\leqslant n\leqslant {10}^6,D\leqslant L\leqslant {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\n",ans);

	}

	return 0;

}

rp++

巴特西