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;  }

(adsbygoogle = window.adsbygoogle || []).push({});