River Jumping【贪心+模拟】

题目链接

  我们可以贪心的从前往后，每次选最接近的且满足条件的这样的贪心，然后从后往前的时候，就是直接用倒着一个个判断是否合法即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 1e5 + 7;
int N, M, S, a[maxN], col[maxN];
set<int> st;
set<int>::iterator it;
vector<int> ans;
int main()
{
    scanf("%d%d%d", &N, &M, &S);
    for(int i=1; i<=M; i++) { scanf("%d", &a[i]); col[a[i]] = i; }
    a[++M] = N; a[0] = 0; col[N] = M; col[0] = 0;
    for(int i=0; i<=M; i++) st.insert(a[i]);
    bool ok = true; int pos = 0;
    while(ok && pos ^ N)
    {
        it = st.lower_bound(pos + S);
        if(it == st.end()) { ok = false; break; }
        pos = *it;
        ans.push_back(col[pos]);
        st.erase(it);
    }
    int nex_pos;
    while(!st.empty())
    {
        nex_pos = *st.rbegin();
        if(pos - nex_pos < S) { ok = false; break; }
        ans.push_back(col[nex_pos]);
        pos = nex_pos;
        st.erase(nex_pos);
    }
    if(pos) ok = false;
    int len = (int)ans.size();
    if(ok && len == M + 1)
    {
        printf("YES\n");
        for(int i=0; i<len; i++) printf("%d%c", ans[i], i == len - 1 ? '\n' : ' ');
    }
    else printf("NO\n");
    return 0;
}