Draw Your Cards

原题链接

题目描述

现有n张牌叠在一起，每次从最上面取出一张牌（上面的值为x），面朝上放在桌上，放置规则为：

找到已经在桌上的牌中第一个>=x的，叠在上面(更新该处的值)
若每日找到符合要求的，则新开一堆（单张牌放着）
如果某一堆摊开的牌个数达到了k，就可以把这一堆拿走

按照牌序号1-n的顺序输出该牌是什么时候被拿走的,没被拿走的牌则输出-1

输入样例

5 2
3 5 2 1 4

输出样例

4
3
3
-1
4

---

算法

(链式存储 + 二分查找)

模拟。set 维护每一堆牌的数量以及顶部的那张牌的值
二分查找值来实现更新

有一个不太好处理的点，就是在拿走k张牌的时候，如何找到路径呢？
那么可以用一个数组来迭代保存路径（有点像链表一样，往回找）

然后因为取牌是有顺序的，所以可以在线处理

注意：要用set自带的lower_bound,效率比 < algorithm > 头文件带的lower_bound 会高很多很多

C++ 代码

时间复杂度 $O(nlogn)$

#include <iostream>
#include <cstring> 
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef pair<int,int> PII;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    vector<int> card(n + 10,-1),cnt(n + 10,0),store(n + 10,-1);
    set<int> s;

    for (int i = 1;i <= n;i ++ ) {
        int p;
        scanf("%d",&p);
        auto key = s.upper_bound(p);//一定要用set自带的upper_bound
        if (key == s.end()) {//end是最后一个的下一个
            s.insert(p);
            cnt[p] = 1;
        }else {//只存最上面的值，且利用指针存下面的值
            store[p] = (*key);
            cnt[p] = cnt[(*key)] + 1;
            s.erase(key);
            s.insert(p);
        }

        if (cnt[p] == k) {
            s.erase(p);
            int x = p;
            for(int j = 0;j < k;j ++){
                card[x] = i;
                x = store[x];//不断迭代下面的存储的值
            }
        }
    }

    for (int i = 1;i <= n;i ++ ) printf("%d\n",card[i]); 
    return 0;
}