题解 P4753 【River Jumping】

时间:2022-09-08 06:32:43

这道神奇的模拟题,带一点贪心,其实蛮水的,仔细思考就能ac。

首先我们模拟一下样例2

发现其实答案0 1 2 3也可以,仔细观察题目,我们发现了一句有意思的话:允许输出任意一组答案。

所以就可使用xjb算法,复杂度为O(玄学)(逃

我们假装有两个小D;一个从0开始跳;一个从n开始跳; 只要距离大于s且没被跳过就跳,之所以说是贪心是因为 我们尽可能让小D1号多跳一点石头,小D2号少跳一点(当然可以反过来),最后扫一遍,如果有石头没跳,就输出“NO”,反之就输出“YES”,然后再按小D1号再到小D2号的顺序输出,核心如下

  for(int i=;i<=n;i++)
if(i-pos>=s&&flag[i]==)
{flag[i]=;ans[now]=a[i];now++;pos=i;}
pos=n;
for(int i=n;i>=;i--)
if(pos-i>=s&&flag[i]==)
{flag[i]=;ans[now]=a[i];now++;pos=i;}

值得一提的是,起点0和终点n也算石头,但是0最后输出,详见代码。

 #include<bits/stdc++.h>//万能头文件,noip不能用
#define maxn 100010
using namespace std;
int a[maxn],ans[maxn];//a记录石头序号,ans记录跳的顺序(即跳的石头序号)
bool flag[maxn];//记录可不可以跳
inline void read(int &x){//快读
x=;int f=;
char ch=getchar();
while(ch<''||ch>''){
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<=''){
x=x*+ch-'';
ch=getchar();
}x*=f;
}
int main(){
//memset(flag,0,sizeof(flag));
int n,m,s,x,pos=n,now=;//pos是当前位置,now是已跳石头个数
read(n);read(m);read(s);
for(int i=;i<=m;++i)
{read(x);flag[x]=;a[x]=i;}//flag==1代表可以跳
flag[]=;flag[n]=;
a[]=;a[n]=m+;//初始化,0和n也算石头
for(int i=;i<=n;i++)
if(i-pos>=s&&flag[i]==)
{flag[i]=;ans[now]=a[i];now++;pos=i;}
pos=n;
for(int i=n;i>=;i--)
if(pos-i>=s&&flag[i]==)
{flag[i]=;ans[now]=a[i];now++;pos=i;}//上已讲解
for(int i=;i<=n;i++)
if(flag[i]==) {printf("NO");return ;}//有石头没跳
printf("YES\n");
for(int i=;i<=now-;i++)
printf("%d ",ans[i]);
}