题解 P4753 【River Jumping】

FlierKing · 2018-07-14 23:28:03 · 题解

首先我们考虑最靠近开头和最靠近结尾的两块岩石，如果他们离开头/结尾的距离小于 S，那么这块岩石将不可能被跳到，从而导致无解。

对于三个连续的岩石 i,i+1,i+2，如果w_{i+2}-w_i<S ，由于我们只能来回一次，且每次跳到其中的一个石头上时必然不可能跳到另一个石头上，所以这种情况也会导致无解。

那么有解时我们只需要贪心地能跳就选择一个距离不小于 S 的且最近的跳就可以了。

时间复杂度 O(N)

#include <bits/stdc++.h>
#define ll long long
#define MAXN 100005
using namespace std;
    int n,m,s,p,cnt;
    int a[MAXN],f[MAXN];
    bool u[MAXN];
int inline read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int main()
{
    n=read(),m=read(),s=read();
    for (int i=1;i<=m;i++)
        a[i]=read();
    sort(a+1,a+m+1);
    a[0]=0,a[m+1]=n;
    for (int i=1;i<=m+1;i++)
        if (a[i]-p>=s)
        {
            f[++cnt]=i;
            p=a[i];
            u[i]=true;
        }
    if (p!=a[m+1])
    {
        puts("NO");
        return 0;
    }
    for (int i=m;i>=0;i--)
        if (!u[i]&&p-a[i]>=s)
        {
            f[++cnt]=i;
            p=a[i];
            u[i]=true;
        }
    if (cnt<m+2)
        puts("NO");
    else
    {
        puts("YES");
        for (int i=1;i<=m+2;i++)
            printf("%d%c",f[i],i==m+2?'\n':' ');
    } 
    return 0;
}