思路 贪心：按照1~n的顺序依次选择一个宝石放入第$i$个盒子（宝石值最大且min(i) - j <= k，否则盒子为空） step b用于保存a[1~n]离散化后的值，然后将a中值相同的放在一起。 用线段树维护当前不同宝石值对应的最小下标，对于第$i$个盒子，宝石的下标满足$ j <= k + i $，查找到最右边的宝石（即满足条件最大值的宝石）下标即为答案 当某一值的宝石用完，可以将线段树中值置为INF（大于 k即可） ``` #include <bits/stdc++.h> using namespace std; #define lson u << 1 #define rson u << 1 | 1 const int N = 100010, INF = 0x3f3f3f3f; int n, k; int a[N], idx[N], b[N], tr[N << 2]; vector<int> g[N]; void pushup(int u) { tr[u] = min(tr[lson], tr[rson]); } void build(int u, int l, int r) { if (l == r) tr[u] = g[l].back(); else{ int mid = (l + r) >> 1; build(lson, l, mid), build(rson, mid + 1, r); pushup(u); } } void update(int u, int l, int r, int x, int v) { if (l == r) tr[u] = v; else { int mid = (l + r) >> 1; if (x <= mid) update(lson, l, mid, x, v); else update(rson, mid + 1, r, x, v); pushup(u); } } int query(int u, int l, int r, int x) { if (l == r) return tr[u]; int mid = (l + r) >> 1; if (tr[rson] <= x) return query(rson, mid + 1, r, x); else if (tr[lson] <= x) return query(lson, l, mid, x); return -1; } int main() { scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } sort(b + 1, b + 1 + n); int len = unique(b + 1, b + 1 + n) - b - 1; for (int i = n; i >= 1; i--) { int x = lower_bound(b + 1, b + 1 + len, a[i]) - b; idx[i] = x; g[x].emplace_back(i); } build(1, 1, len); for (int i = 1, last = 0; i <= n; i++) { int x = query(1, 1, len, i + k); if (x != -1 && a[x] == a[last]) { update(1, 1, len, idx[x], INF); x = query(1, 1, len, i + k); update(1, 1, len, idx[last], g[idx[last]].back()); } if (g[idx[i]].size() && g[idx[i]].back() == i) { g[idx[i]].pop_back(); int v = g[idx[i]].size() ? g[idx[i]].back():INF; update(1, 1, len, idx[i], v); } if (x != -1 && g[idx[x]].size() && g[idx[x]].back() == x) { g[idx[x]].pop_back(); int v = g[idx[x]].size() ? g[idx[x]].back():INF; update(1, 1, len, idx[x], v); k -= x - i; // cout<<"F"<<endl; } last = x == -1 ? 0:x; if (x == -1) printf("-1 "); else printf("%d ", a[x]); } return 0; } ```