[原题链接](https://atcoder.jp/contests/abc260/tasks/abc260_d "原题链接") ### 题意 现有n张牌叠在一起，每次从最上面取出一张牌（上面的值为x），面朝上放在桌上，放置规则为： 1. 找到已经在桌上的牌中第一个>=x的，叠在上面(更新该处的值) 2. 若每日找到符合要求的，则新开一堆（单张牌放着） 3. 如果某一堆摊开的牌个数达到了k，就可以把这一堆拿走 按照牌序号1-n的顺序输出该牌是什么时候被拿走的,没被拿走的牌则输出-1 ### 分析 模拟。set 维护每一堆牌的数量以及顶部的那张牌的值 二分查找值来实现更新 有一个不太好处理的点，就是在拿走k张牌的时候，如何找到路径呢？ 那么可以用一个数组来迭代保存路径（有点像链表一样，往回找） 然后因为取牌是有顺序的，所以可以在线处理 ##### 注意：要用set自带的lower_bound,效率会高很多很多 ### Code ```cpp #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int N = 2e5 + 5; int cnt[N], nxt[N]; //数量 路径 int main () { int n, k; cin >> n >> k; vector <int> ans (n+1, -1); set <int> table; //维护桌上的最大值 for (int i = 1; i <= n; i ++) { int x; cin >> x; if (k == 1) { ans[x] = i; continue; } auto pos = table.lower_bound (x); //cout << "pos=" << *pos << endl; //开一叠新的 if (pos == table.end()) { table.insert (x); cnt[x] ++; } //叠上+更新值 else { nxt[x] = *pos; cnt[x] = cnt[*pos] + 1; table.erase (pos), table.insert (x); } //能被拿走 if (cnt[x] == k) { table.erase(x); int tk = k, tx = x; while (tk --) { ans[tx] = i; tx = nxt[tx]; } } } for (int i = 1; i <= n; i ++) cout << ans[i] << endl; } //很像蜘蛛纸牌 // 把最上面的牌拿出来，上面的值为x // 找到已经翻开的牌中第一个>=x的，叠在上面(更新该处的值) // 如果某一堆摊开的牌个数达到了k // 1-n输出该牌是什么时候被吃掉的,没被吃掉则输出-1 // 模拟+二分查找 ```