C++贪心算法:最小新整数

最小新整数

Description

给定一个十进制正整数n(0 < n < 1000000000)，每个数位上数字均不为0。n的位数为m。
现在从m位中删除k位(0<k < m)，求生成的新整数最小为多少？
例如: n = 9128456, k = 2, 则生成的新整数最小为12456

Input

第一行t, 表示有t组数据；
接下来t行，每一行表示一组测试数据，每组测试数据包含两个数字n, k。

Output

t行，每行一个数字，表示从n中删除k位后得到的最小整数。

Sample Input

2
9128456 2
1444 3

Sample Output

12456
1

思路解析

      由于正整数n需要删除它一些数位上的数，所以可以采用字符串类型来存储n。那么，应如何来确定该删除哪k位呢？是不是只要删掉最大的k个数字就可以了呢？
      为了尽可能地逼近目标，我们选取的贪心策略为：每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字，否则删除第一个递减区间的首字符。然后回到串首，按上述规则再删除下一个数字。重复以上过程k次，剩下的数字串便是问题的解了。

代码实现

#include<iostream>
using namespace std;
int k;
main()
{
	int t;
	cin>>t;
	while(t--)
	{
		string n; //定义字符串n
		cin>>n>>k;
		int len=n.size(); //也可以用n.length()来取字符串n的长度
		while(k--)
			for(int i=0;i<len;i  ) //枚举
				if(n[i]>n[i 1]||i==len-1) //删除遇到的第一个递减序列的第一个数字(若整个字符串为非递减序列，则删去末尾的数字)
				{
					n.erase(i,1); //把当前字符从字符串中删除
					break; //不可省略，否则字符串会多删字符
				}
		while(n[0]=='0'&&n[1]) //去掉前缀0，并至少保留1个数字
			n.erase(0,1); //删去当前字符串开头的'0'
		cout<<n<<endl; //输出字符串
	}
}

这篇好文章是转载于：学新通技术网