「LuoguP4753」濑 River Jumping（贪心

Description

有一条宽度为 N 的河上，小D位于坐标为 0 的河岸上，他想到达坐标为 N 的河岸上后再回到坐标为 0 的位置。在到达坐标为 N 的河岸之前小D只能向坐标更大的位置跳跃，在到达坐标为 N 的河岸之后小D只能向坐标更小的位置跳跃。在河的中间有 M 个岩石，小D希望能跳到每个岩石上恰好一次。由于小D的跳跃能力太强，小D的跳跃长度有个下限 S ，但没有上限。现在请你判断他是否能够完成他的目标。

Input

第一行输入两个整数 N,M,S，分别表示河的宽度，岩石的数量和跳跃长度的下限。

第二行输入 M 个整数，分别表示 M 个岩石的坐标 w1,w2,⋯,wN 。保证 { wi }为递增序列。

Output

如果小D可以完成他的目标，第一行输出YES，第二行输出 M+2 个数，依次表示小D跳到的石头编号。特殊的，坐标为 0 的河岸编号为 0 ，坐标为 N 的河岸标号为 M+1 。如果有多种解法，允许输出任意一种。

如果小D不能完成他的目标，第一行输出NO。

Sample Input1

6 1 3
3

Sample Output1

YES
1 2 0

Sample Input2

6 2 2
2 4

Sample Output2

YES
2 3 1 0

Sample Input3

5 2 3
2 3

Sample Output3

Hint

1≤N,S≤100000

0 ≤ M < N

1 ≤ wi < N

题解

O(n) 贪心

把一个人来回跳看作两个青蛙一起跳。

设两只青蛙所在的坐标为 xa , xb。

我们先假设青蛙已经跳了一段路程，且设xa < xb ，面前的最近石块坐标为x
那么有且仅有3种情况：
1: x - xa< s(a青蛙踩不到x)，此时 x - xb < s，那么x石块怎样都踩不到，输出NO。
2:x - xa > s 且 x - xb < s(a能踩 b不能踩)，那么a青蛙跳到x石块，xa = x 。
3:x - xa > s且 x - xb > s(a,b都能踩)，此时可以跳a也可以跳b，但把青蛙a保留在xa 而让b跳到x，比保留b 而让a跳到x对未来有更大的潜力（因为xa < xb，所以xa能跳到的区间比xb大）

那么思路就清晰了：

初始时xa=xb=0。扫描坐标w，对于一个新扫入的坐标值，判定以上三种情况并作出相应决策，把两只青蛙经过的坐标分别存储为 a , b数组。

输出时假装a青蛙正着跳，b青蛙反着跳，0坐标和河对岸手动输出。

注意以上的假设基于 xa < xb的前提，写代码的时候不要思维僵化。

AC代码：

#include<iostream>

#include<cstdio>

using namespace std;

#define R register

inline int read()

{

    char ch=getchar();

    int x=0;bool s=1;

    while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}

    return s?x:-x;

}

int a[100007];

int b[100007];

int toa=0,tob=0;

int main()

{

    int n=read(),m=read(),s=read();

    int xa=0,xb=0;//一开始都在河岸这边

    for(R int i=1;i<=m;++i)

    {

        int x=read();

        if(xa<xb)//如果xa<xb

        {

            if(x-xa<s){cout<<"NO";return 0;}//case 1

            else if(x-xb<s){a[++toa]=i;xa=x;}//case 2

            else {b[++tob]=i;xb=x;}//case 3

        }

        else//如果xb<=xa

        {

            if(x-xb<s){cout<<"NO";return 0;}//case 1

            else if(x-xa<s){b[++tob]=i;xb=x;}//case 2

            else {a[++toa]=i;xa=x;}//case 3

        }

    }

    if(n-xa<s&&n-xb<s){cout<<"NO";return 0;}//有青蛙跳不上对岸 输出NO

    cout<<"YES"<<endl;

    for(R int i=1;i<=toa;++i)

    cout<<a[i]<<" ";//a正跳

    cout<<m+1<<" ";

    for(R int i=tob;i;--i)

    cout<<b[i]<<" ";//b反跳

    cout<<0;

    return 0;

}

巴特西