Draw Your Cards

_shine_ · 2023-05-09 16:21:09 · 题解

1. 题目大意

依次摸 n 张卡牌，并且维护一些牌堆，如果找到大于 p_i 最小的一张，那就把 p_i 放到这个堆的堆顶，反之就新开一堆，放入 p_i。如若牌堆个数等于 k，就删去这堆牌。现在问你在 n 步中，每张牌删去的时间

2. 思路

最容易想到，考虑本题目中使用暴力。

在每一次枚举没一个数 p_i，同时在此，枚举牌堆中的其他数 p_j，判断 p_j 是否小于 p_i，并且纳入牌堆即可。

TLE Code

但是注意，在本题中，用此思路会使得本题不通过，思考优化本题，不难发现，在本题目中，如若 p_i<k，则不用枚举 p_i，因为就所有连着从 p_i 到 1，也不可能使得牌堆大小大于 k，再交即可通过。

AC Code

#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*w;
}
inline void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x % 10 + '0');
}
const int maxn=2e5+10;
int n,k,p[maxn];
int ans[maxn];
bool vis[maxn];
signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i){
        p[i]=read();
    }
    for(int i=1;i<=n;++i){
        if(vis[p[i]]==0 && p[i]>=k){
            vis[p[i]]=1;
            vector<int>e;
            e.push_back(p[i]);
            int now=k-1,last=p[i],last_time=i;//last_time用来记录时间，last记录牌堆的上一个，now防止牌堆个数大于k
            for(int j=i+1;now>0 && j<=n;++j){
                if(last>p[j] && vis[p[j]]==0){//枚举牌堆中的数
                    last=p[j];
                    vis[p[j]]=1;
                    now--;
                    e.push_back(p[j]);
                    last_time=j;//更新，记录新的p[j]
                }
            }
            if(now==0){//输出
                for(int j=0;j<e.size();++j){
                    ans[e[j]]=last_time;//记录牌堆删除时间
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        if(ans[i]==0)ans[i]=-1;//为了避免初始化，所以在此判断p[i]是否在牌堆中被删除。
        printf("%d\n",ans[i]);//输出
    }
    return 0;
}