2021蓝桥杯模拟赛-删除字符

题目

题目链接

题解

贪心。

贪心思路：

将整个字符串视为若干段降序排列的子串，即

从左边开始向右遍历，遇到逆序的就删除，再对新的串从头遍历找逆序，不停地重复整个过程是为了保证删除的尽可能靠前（贪心），如果整个字符串都顺序了，但是还要删，那么就从后面开始删，保留前面小的。

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	int t;
	
	cin >> s;
	cin >> t;
	
	while (t --) {
		int flag = 0;
		for (int i = 0;i < s.size()-1;i ++)
			if (s[i] > s[i+1]) {
				s.erase (i, 1);
				flag = 1;
				break;
			}
		if (!flag) break;
	}
	for (int i = 0;i < s.size () - t - 1;i ++)
		cout << s[i];

	return 0;
}