有一条宽度为 N 的河上，小D位于坐标为 0 的河岸上，他想到达坐标为 N 的河岸上后再回到坐标为 0 的位置。在到达坐标为 N 的河岸之前小D只能向坐标更大的位置跳跃，在到达坐标为 N 的河岸之后小D只能向坐标更小的位置跳跃。在河的中间有 M 个岩石，小D希望能跳到每个岩石上恰好一次。由于小D的跳跃能力太强，小D的跳跃长度有个下限 S ，但没有上限。现在请你判断他是否能够完成他的目标。
第一行输入两个整数 N,M,S，分别表示河的宽度，岩石的数量和跳跃长度的下限。
第二行输入 M 个整数，分别表示 M 个岩石的坐标 w1,w2,⋯,wN 。保证 { wi }为递增序列。
如果小D可以完成他的目标，第一行输出YES，第二行输出 M+2 个数，依次表示小D跳到的石头编号。特殊的，坐标为 0 的河岸编号为 0 ，坐标为 N 的河岸标号为 M+1 。如果有多种解法，允许输出任意一种。
如果小D不能完成他的目标，第一行输出NO。
6 1 3 3
YES 1 2 0
6 2 2 2 4
YES 2 3 1 0
5 2 3 2 3
NO
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; }转载于:https://www.cnblogs.com/qwerta/p/9379752.html
