我们可以贪心的从前往后，每次选最接近的且满足条件的这样的贪心，然后从后往前的时候，就是直接用倒着一个个判断是否合法即可。
#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; }
