自动搬运

查看原文

来自洛谷，原作者为

	Starw 弱小和无知不是生存的障碍，傲慢才是|NOIP2024RP++

搬运于2025-08-24 22:35:47，当前版本为作者最后更新于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$ 还有剩余的情况