4.最小新整数（smallest.cpp）

【题目描述】

假如：有一个十进制正整数n,每个数位上数字均不为0，并且0<n<1000000000。n的位数为m。先在从m位中删除k位（0<k<m）,求生成的新整数最小为多少？

如：n=9128456,k=2，则生成的新整数最小为12456。

【输入描述】

第一行t,表示有t组数据；

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

【输出描述】

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

【样例输入】

2
9128456 2
1444 3

【样例输出】

12456
1

【题目分析】

• 贪心算法中的字典序类问题

• 要整数最小，那么最高位要最小，次高位要在此基础上再最小……因此，我们可以先确定最高位的数，在确定次高位的，这样一直下去，知道整个数确定为止。

• 一个数字有n位，删除m位，也就是保留n-m位。

  
  

【参考代码1】

#include<bits/stdc++.h>
using namespace std;
int main() {
	int i, n, len, t;
	char a[105];
	int cnt;
	cin>>cnt;
	while(cnt--) {
		cin>>a>>n;
		t = n;
		len = strlen(a);
		if(len <= t) { //要删除的数量大于总长度，直接为0
			printf("0\n");
			continue;//及时跳出
		}
		while(n--) {
			i = 0;
			while(a[i] <= a[i + 1]) { //由左到右找到第一个最大的数(所在分位最大)
				i++;
			}
			for(; i < len; i++) { //删除此(相比较的最大分位)最大值
				a[i] = a[i + 1];
			}
			len--;
		}
		printf("%s\n", a);
	}
	return 0;
}

【参考代码2】

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char str[100];
int main()
{
    int t,n;
    cin>>t;
    while(t--)
    {
        cin>>str>>n;
        int len=strlen(str);
        while(n--)
        {
            for(int i=0;i<len-1;i++)
                if(str[i]>str[i+1])
                {
                    for(int j=i;j<len-1;j++)
                        str[j]=str[j+1];
                    break;
                }
            len--;
        }
        str[len]='\0';
        cout<<str<<endl;
    }
    return 0;
}