P8082 [COCI2011-2012#4] KEKS

Starw · 2022-01-29 21:04:05 · 题解

思路：

我们贪心地想，要想要删完后的这个数越大，那么越在前面的数就要越大，那我们就可以用一个单调栈，不断将栈顶的数弹出，一直到删数次数为 0 或栈空或栈顶的数比要加入的数大，然后加入那个数，最后遍历一次栈，还要考虑 k 还有剩余的情况，做法就是把后面还剩下的 k 个数不统计，所组成的数就为答案。

代码：

#include<bits/stdc++.h>
#define MAXN 500005
using namespace std;
char s[MAXN];
int st[MAXN],top;//栈 
int main(){
    int n,k;
    scanf("%d%d%s",&n,&k,s+1);
    for(int i=1;i<=n;i++){
        int x=s[i]-'0';
        while(k&&top&&st[top]<x)k--,st[top--]=0;//弹出操作 
        st[++top]=x;//加入操作 
    }
    for(int i=1;i<=top-k;i++)//遍历栈 不遍历后面剩余的 k 个数
        printf("%d",st[i]);//输出答案 
    return 0;
}

upd on 2024.8.13 修了 k 还有剩余的情况