【解题报告】洛谷 P4753 River Jumping

【解题报告】洛谷 P4753 River Jumping

原题链接

https://www.luogu.com.cn/problem/P4753

题目大意

一条宽度为 \(n\) 的河上,有 \(m\) 块石头,每块石头距离起点(坐标为0)有一个距离,我们要从起点跳到终点,通过一些方法使得跳到每个石头上一次,最终回到起点,每次跳的距离有一个下限 \(s\) ,输出一种可能的方案

思路

看到这道题目,我们首先关注到的是一个下限 \(s\) ,为什么我们要关注这个呢?因为,我们可以发现,如果你想跳的石头与你的距离 \(d \ge s\) 你是不是就可以随便跳?

于是我们自然而然地想,我们是不是可以使用贪心算法?

每次跳,跳到一个距离自己第一个 \(\ge s\) 的石头上,一直向右,到右边了之后,我们再向左重复上述过程。因为在能完成的情况下我们跳到最右边的时候,离左边的距离一定大于 \(s\) ,所以我们可以跳过去,然后再跳回来,反复横跳,最后就能完成了

那么,我们还要处理不能完成的情况,那么我们什么情况不能完成呢?

  • 最左边的石头和 \(0\) 距离小于 \(s\) ,或者最右边的石头和 \(n\) 的距离小于 \(s\)
  • 有连续三个石头之间的距离小于 \(s\) ,因为这样总有一个石头跳不到
  • \(0\) 和 \(n\) 的距离小于 \(s\) ,实际上这个是严格被第一个不能完成的条件包含的

这样,我们找到了所有不能完成的情况

接着,我们进行一个暴力,从 \(0\) 开始跳,每次判断是否能跳,如果能跳的话,标记一个 \(vis=true\) 表示已经访问过了,如果已经访问过了,那就访问下一个石头能不能跳.跳到 \(n\) 之后反过来向 \(0\) 跳.对于这个过程使用一个 \(while\) 循环就可以了,我们每次循环开头判断一下是否每个石头都走了,如果都走了,那我们退出循环

至于输出的话,一定要记得不要先输出 \(0\) ,它永远都是最后一个,然后我们把输出放在循环里面边跳边输出就可以了

这道题目我昨天干了两个多小时,一直被不能完成的条件所困,请大家一定要注意条件!!!

好的,管理员大大求过

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;
const int maxn=100005;
int n,m,s;
int w[maxn];
int cnt=0;
bool vis[maxn];
bool flag=false;
bool check()
{
	for(int i=0;i<=m+1;i++)
	if(!vis[i])
	return false;
	return true;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	cin>>n>>m>>s;
	
	for(int i=1;i<=m;i++)
	{
		cin>>w[i];
		if(w[i]-w[i-1]<s)
		cnt++;
		else
		cnt=0;
		if(cnt>=3) flag=true;
	}
	w[0]=0;w[m+1]=n;
	
	if(n<s)
	{
		cout<<"NO"<<'\n';
		return 0;
	}
	
	if(m!=0&&(w[1]<s||n-w[m]<s))
	{
		cout<<"NO"<<'\n';
		return 0;
	}
	/*if(m==2)
	{
		if(w[m]-w[m-1]<s)
		{
			cout<<"NO"<<'\n';
			return 0;
		}
	}*/
	if(flag)
	{
		cout<<"NO"<<'\n';
		return 0;
	}
	cout<<"YES"<<'\n'; 
	int last=0;
	int tot=1;
	while(!check())
	{
		for(int i=1;i<=m+1;i++)
		{
			if(w[i]-w[last]>=s&&!vis[i])
			{
				cout<<i<<" ";
				vis[i]=true;
				last=i;
			}
			else continue;
		}
		for(int i=last;i>=0;i--)
		{
			if(w[last]-w[i]>=s&&!vis[i])
			{
				cout<<i<<" ";
				vis[i]=true;
				last=i;
			}
		}
	}
	
	return 0;
}
上一篇:(剑指offer)合并两个排序的链表


下一篇:L3:查找