出题人题解 | #青蛙#

原题解链接：https://ac.nowcoder.com/discuss/149978

先考虑如何判断有$xx$只青蛙要从起点跳到终点是否可行。

我们从左往右考虑每块石头,

1.可以强制使用这块石头,因为不用这块石头的方案可以转化成使用这块石头的方案;

2.可以强制让最左的青蛙跳到这块石头,因为让非最左的青蛙跳到这块石头的方案可以转化成让最左的青蛙跳到这块石头的方案。

可以发现青蛙一直是连续的一段,所以到第$ii$块石头的时候判断一下和第$i-xi\; -\; x$块石头的距离就行了。

时间复杂度$O(m)O(m)$。 现在回到原问题。 直接二分就可以做到$O(tmlogm)O(tmlogm)$了,但还可以更好。

记$f(i)=minjf(i)\; =\; min\; j$满足考虑到第$ii$块石头时，存在方案使得$j\mathrm{.}\mathrm{.}ij..i$都有青蛙。 求出$f(m)f(m)$就可以求解答案了。 考虑已经求出$f(i-1)f(i-\; 1)$,现在要求$f(i)f(i)$。

int j=f(i-1);
while(x(i)-x(j)>d)++j;
++j;

就好了( $x(i)x(i)$表示第$ii$块石头的坐标)。

详见$stdstd$。

时间复杂度$O(tm)O(tm)$。

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
const int N=3e5+5;
int a[N];

int main()
{
//	freopen("1.in","r",stdin);
	int tt;
	cin>>tt;
	while(tt--)
	{
		int n,m,d;
		cin>>n>>m>>d;
		rep(i,0,m+1)scanf("%d",a+i);
		int i=0;
		while(a[i+1]<=d+1)++i;
		int j=1;
		while(i>=j&&i<m)
		{
			++i;
			while(a[i]-a[j]>d)++j;
			++j;
		}
		if(j>i)puts("0");
		else
		{
			while(n-a[j]>d)++j;
			printf("%d\n",m-j+1);
		}
	}
}