P4753 River Jumping 题解

CSDN同步

原题链接

简要题意:

一条宽度为 (L) 的河上有若干石头,每次只能在石头上跳跃(一开始从 (0) 开始跳),且跳跃距离的下限为 (S).问能否一个来回将所有石头(包括河对面的那块)全跳一遍;如果能,则输出方案。

算法一

二分。

注意到,我们可以对 跳跃上限 进行二分。

然后贪心地,每次跳 在下限之上离自己最近的 一块石头。

当然如果 这块石头距离超过上限 说明当前验证无解。

然后记录答案即可。

时间复杂度:(O(n log n)).

实际得分:(100pts).

代码就不给出了,因为 博主太懒了 并不是最优的。

算法二

既然不求上限,为什么要二分上限呢?

反正上限是不固定的,不必二分它,而且我们并不关心上限是多少这个问题。

下面考虑贪心。

你想,假设你在 (x) 的位置,离你最近的两块石头是 (y < z),且满足 (y - x geq S)(z -y geq S),你会选择?

显然是选择 (x ightarrow y ightarrow z) 这样子。

那么你说:如果不跳 (y),给回头路踩呢?

这是不对的,因为 (z) 后面的石头肯定和 (y) 的距离 (geq S),回来的时候可以直接不跳 (y),这是因为没有上限!

所以,每次跳最多的石头就是最优的。

时间复杂度:(O(n)).

实际得分:(100pts).

具体细节见代码。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int N=1e5+2;

inline int read(){char ch=getchar();int f=1;while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();}
	int x=0;while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}

int a[N],n,L,S;
bool h[N]; int fir;
int jump[N],f=0;

int main(){
	L=read(),n=read(),S=read();
	for(int i=1;i<=n;i++) a[i]=read();
	a[0]=0; a[n+1]=L;
	for(int i=1;i<=n+1;i++) 
		if(a[i]-fir>=S) { //能跳就跳
			jump[++f]=i; //记录答案
			fir=a[i]; //fir 记录当前跳到的位置
			h[i]=1; //标记,回头不再跳过
		}
	if(fir!=a[n+1]) {puts("NO");return 0;} //没跳到头,结束
	for(int i=n;i>=0;i--)
		if(!h[i] && fir-a[i]>=S) { //没有标记过,跳
			jump[++f]=i;
			fir=a[i];
			h[i]=1;
		}	//同理
	if(f<n+2) {puts("NO");return 0;} //没有跳完
	puts("YES");
	for(int i=1;i<=f;i++)
		printf("%d ",jump[i]);	//输出答案
	return 0;
}

原文地址:https://www.cnblogs.com/bifanwen/p/12610763.html