【解题报告】洛谷 P4753 River Jumping
原题链接
https://www.luogu.com.cn/problem/P4753
题目大意
一条宽度为 n 的河上，有 m 块石头，每块石头距离起点（坐标为0）有一个距离，我们要从起点跳到终点，通过一些方法使得跳到每个石头上一次，最终回到起点，每次跳的距离有一个下限 s ,输出一种可能的方案
思路
看到这道题目，我们首先关注到的是一个下限 s ，为什么我们要关注这个呢？因为，我们可以发现，如果你想跳的石头与你的距离 d≥s 你是不是就可以随便跳？
于是我们自然而然地想，我们是不是可以使用贪心算法？
每次跳，跳到一个距离自己第一个 ≥s 的石头上，一直向右，到右边了之后，我们再向左重复上述过程。因为在能完成的情况下我们跳到最右边的时候，离左边的距离一定大于 s ，所以我们可以跳过去，然后再跳回来，反复横跳，最后就能完成了
那么，我们还要处理不能完成的情况，那么我们什么情况不能完成呢？
- 最左边的石头和 0 距离小于 s ，或者最右边的石头和 n 的距离小于 s
- 有连续三个石头之间的距离小于 s ，因为这样总有一个石头跳不到
- 0 和 n 的距离小于 s ，实际上这个是严格被第一个不能完成的条件包含的
这样，我们找到了所有不能完成的情况
接着，我们进行一个暴力，从 0 开始跳，每次判断是否能跳，如果能跳的话，标记一个 vis=true 表示已经访问过了，如果已经访问过了，那就访问下一个石头能不能跳.跳到 n 之后反过来向 0 跳.对于这个过程使用一个 while 循环就可以了，我们每次循环开头判断一下是否每个石头都走了，如果都走了，那我们退出循环
至于输出的话，一定要记得不要先输出 0 ，它永远都是最后一个，然后我们把输出放在循环里面边跳边输出就可以了
这道题目我昨天干了两个多小时，一直被不能完成的条件所困，请大家一定要注意条件！！！
好的，管理员大大求过
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
| #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(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;
}
|
