Atcoder 题解

Atcoder Beginner Contest 260 problem D题解

题目大意

题目链接:点我

桌面上有$N$张背面朝上的牌，每张牌上有一个数字$P_i$，包含了$1$到$N$中的整数。你将会进行$N$次翻牌操作。每次翻牌时，翻开最上面的一张牌，寻找在桌面上有无数字大于等翻开的数字的正面朝上的牌。若有，则把翻开的牌正面朝上，放在符合条件的牌中数字最小的牌上(覆盖它)。若没有，则把牌正面朝上，放在桌面上。若某时某刻，桌面上一堆正面朝上的牌中牌的数量$\geq K$，则吃掉这堆牌。对$i=1,2,3,…,N$,输出牌上数字为$i$的牌被吃掉时的操作数。做操做完后牌上数字为$i$的牌没有被吃掉，则输出$-1$。

输入$N,K$和$N$个整数$P_i$。

样例输入1

5 2
3 5 2 1 4

样例输出1

4
3
3
-1
4

样例解释1

• 第一次，翻第一张牌，得到数字$3$。桌面上没有正面朝上的牌，则把$3$正面朝上放桌子上。此时桌上的牌堆有{$3$}。

• 第二次，翻第二张牌，得到数字$5$。桌面上正面朝上的牌中，没有$\geq 5$的，则把$5$正面朝上放桌子上。此时桌上的牌堆有{$3$}，{$5$}。

• 第三次，翻第三张牌，得到数字$2$。桌面上正面朝上的牌中，$3$、$5$都大于$2$，但$3$更小，于是将$2$放在$3$上。此时桌上的牌堆有{$3,2$}，{$5$}。

  • 因为第一堆牌的数量达到了$K$， 则吃掉第一堆牌。$ans[2]$和$ans[3]$更新为$3$。

• 第四次，翻第四张牌，得到数字$1$。桌面上正面朝上的牌中，只有$5$大于$1$，于是将$1$放在$5$上。此时桌上的牌堆有{$5$，$1$}。

  • 因为第一堆牌的数量达到了$K$， 则吃掉第一堆牌。$ans[1]$和$ans[5]$更新为$4$。

• 第五次，翻第五张牌，得到数字$4$。桌面上没有正面朝上的牌，则把$4$正面朝上放桌子上。此时桌上的牌堆有{$4$}。

由于$4$没有被吃掉，第$4$行应输出$-1$。

样例输入2

5 1
1 2 3 4 5

样例输出2

1
2
3
4
5

如果$K=1$，那么所有的牌一放到桌子上就会被吃掉。

样例输入3

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

样例输出3

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

数据范围

• $1 \leq K \leq N \leq 2 \times 10^5$
• 所有输入均为正整数。
• $P$为$1,2,…,N$的一个排列。

解析

妥妥的模拟题。

我们用一个数组来存下当前所有正面朝上的牌堆中最上面的一张牌的数字。因为每一次放牌时，都是找到大于等于这个数的最小的那个数，如果这个数组满足单调性，那么显然在改变之后，数组仍然满足单调性。

因此，我们可以用$STL$中的$set$容器来存储牌堆顶元素。$set$会自动使元素满足单调递增性。因此，在寻找牌堆时，可以使用二分来查找。幸运的是，$set$中自带$lower$_$bound$函数，帮助我们找到要操作的一堆牌。

另外在更新$ans$数组时，由于$set$中只存下了牌顶元素，不知道牌堆中有哪些元素。因此，我们可以另开一个数组$under[i]$，表示数字为$i$的那张牌下的那张牌数字为$under[i]$。如果这张牌是最底下的那一张，则$under[i]$可以为任何数。

然后，我们就可以向下求出这一堆牌中的所有元素。(见下)

for(int j=0;j<k;j++){
    res[x]=i;
    x=under[x];
}

(第一次写时$set$用的是$vector$，不知道怎么删除元素就枚举所有牌堆，$TLE$了四个点(悲伤))

代码实现

#include<iostream>
#include<cstring>
#include<set>
using namespace std;
const int N=2e5+5;
int n,k;
int under[N],res[N]; //under是向下传递数组，res是答案数组
int si[N]; //表示牌顶编号为i的那堆牌的数量
set<int> st;
int main()
{
    memset(under,-1,sizeof under);
    memset(res,-1,sizeof res); //初值都赋为-1
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        auto it=st.lower_bound(p); //用lower_bound找到要放的那一堆牌
        if(it==st.end()){
            st.insert(p);
            si[p]=1; //如果找不到，那么就新建一个牌堆
        }else{
            under[p]=*it; //找到了，就把牌放在这个牌堆上，并更新under数组
            si[p]=si[*it]+1;
            st.erase(it);
            st.insert(p); //将牌顶元素更新为p
        }
        if(si[p]==k){ 
            st.erase(p);
            int x=p;
            for(int j=0;j<k;j++){
                res[x]=i;
                x=under[x];
            }
        }//若牌数达到k,则向下标记元素,并移除这堆牌
    }
    for(int i=1;i<=n;i++) cout<<res[i]<<endl;
    return 0;
}

完结撒花~~~