博客

贪心，找规律

有0的情况，比如 50074897， 删2 个数 ，得到的最小数是 4897， 发现规律：

要删除k个数，而前k个数之间夹着 0， 那么删除最后一个0之前的所有非零数字，

可以使得剩下的数字，有若干个前缀0，比如 50074897 删掉 5 和 7，得到004897 = 4897

所以，先处理而前k个数之间夹着 0的情况。处理完了，假如删除了 y 个非零数字，则还需要删

k -= y 的非零数字。

没有 0的情况，就是不断确定首个数字的过程。以 175438， k = 4 为例子。

删掉4个数字，首个数字，只能是 17543 这几个数字中的一个 ，就是 下标 [0 … 4]

中的一个，从 17543 找到最小的数字 1， 作为首数字，剩下 75438， 还需要删 4个数字。

75438被删掉4个数字，剩下的数的首数字可能是 75438 这几个数字的一个，找到最小的数字3，

754被删掉，剩下数字 8，此时还需要删一位数字，直接把8删掉就好。

综上所述，确定的2个首数字 1 和 3 就是最后剩下来的数字 13

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MaxN = 255;
char str[MaxN], ans[MaxN];
bool has_erase[MaxN];
int n, k;

void solve()
{
	//在 前k个非0数字中夹着的0， 可以直接去掉，能使得数位变小
	n = strlen(str);
	int not_zere = 0, i = 0, last_zero_index = -1;	//last_zero_index 最后一个0的下标
	while(i < n - 1 && str[i] == '0')	//去掉前缀0
	{
		++i;
	}
	int mark_i = i;
	for(; i < n; ++i)
	{
		if(str[i] != '0')
		{
			++not_zere;
			if(not_zere == k)
			{
				break;
			}
		}else{
			last_zero_index = i;
		}
	}
	if(not_zere < k)
	{
		printf("0\n");
		return;
	}
	int erase_cnt = 0;
	for(int x = 0; x <= last_zero_index; ++x)
	{
		if(str[x] != '0')
			erase_cnt++;
		has_erase[x] = true;
	}
	k -= erase_cnt; // 剩下还需要删除的数位
	if(-1 == last_zero_index)
		i = mark_i;
	else
		i = last_zero_index + 1;
	while(k > 0)	//不断的确定首位
	{
		int min_index = i;
		char min_value = 'a';
		for(int x = i; x <= i + k; ++x)	//找到数字值最小的下标
		{
			if(str[x] < min_value)
			{
				min_index = x;
				min_value = str[x];
			}
		}
		for(int x = i; x <= i + k; ++x)
		{
			if(str[x] == min_value)
			{
				has_erase[x] = false;	//这个是首位
				k -= x - i;			//首位数字确定，加上前面有 x - i位数字被删掉
				i = x + 1;
				if(n - i == k)	//剩下的数字都要删掉
				{
					for(int j = i; j < n; ++j)
						has_erase[j] = true;
					k = 0;
				}
				break;
			}else{
				has_erase[x] = true;	
			}
		}
	}
	int j = 0, inx = 0;
	for(int x = 0; x < n; ++x)
	{
		if(has_erase[x] == false)
		{
			ans[inx++] = str[x];		
		}
	}
	while(j < inx - 1 && ans[j] == '0')//去除前缀0
		++j;
	printf("%s\n", ans + j);
}

int main()
{
	scanf("%s", str);
	scanf("%d", &k);
	solve();
	return 0;
}

/*
175438 
4
*/

/*
13
*/