题解 P4753 【River Jumping】

这道神奇的模拟题，带一点贪心，其实蛮水的，仔细思考就能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]);

 }