贪心算法4：删数问题

怼烎@ 2022-05-07 04:58 414阅读 0赞

## 题目描述 ##

键盘输入一个高精度的正整数N，去掉其中任意kk个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和k，寻找一种方案使得剩下的数字组成的新数最小。

输出应包括所去掉的数字的位置和组成的新的整数。（N不超过250位） 输入数据均不需判错。

Simple Input

178543

Simple Output

> 贪心策略：每次删掉的数都要保证删除数后剩下的数最小。即就是每次都要删除第一个递减区间的第一个数。

![70][]

本题容易犯错的地方，不能每次都删除最大的数。

例如：141519 2 //如果删最大的9，5，结果为1411，如果删掉4，5，结果为1119，显然删掉4，5才是最佳答案。

# 删除字符串串首零的方法：[https://blog.csdn.net/yanyanwenmeng/article/details/83052319][https_blog.csdn.net_yanyanwenmeng_article_details_83052319] #

# 删除字符串中的第一个递减区间的数 #

[https://blog.csdn.net/yanyanwenmeng/article/details/83052591][https_blog.csdn.net_yanyanwenmeng_article_details_83052591]

#include<iostream>
    #include<cstring>
    #define MAXN 255
    using namespace std; 
    char a[MAXN];
    int main()
    {
    	//freopen("a.txt","r",stdin);
    	cin >> a;
    	int n = strlen(a);
    	int m;
    	cin >> m;
    	while(m--)
    	{
    		for(int i = 0; i < n; ++i)
    		{
    			if(a[i] > a[i+1]) 
    			{
    				for(int k = i; k < n; ++k)//指针往前移动 
    				{
    					a[k] = a[k+1];
    				}
    			}
    			break;//第一次删数完毕，跳出循环 
    		}
    		--n;		
    	}
    	bool flag = false;
     	for(int i = 0; i < n; ++ i)
     	{
     		if(a[i] != '0') flag = true;//删除串首的零 
     		if(flag) cout << a[i];
    	}
    	if(!flag) cout << "0" << endl;
    	cout << endl;
    	return 0;
    }

[70]: /images/20220506/f95dace268ae47e599ed41819ca46a2b.png
[https_blog.csdn.net_yanyanwenmeng_article_details_83052319]: https://blog.csdn.net/yanyanwenmeng/article/details/83052319
[https_blog.csdn.net_yanyanwenmeng_article_details_83052591]: https://blog.csdn.net/yanyanwenmeng/article/details/83052591