最大数字 题解 （删除k个数字----贪心）

问题 1972: 最大数字

时间限制: 1Sec 内存限制: 128MB 提交: 104 解决: 27

题目描述

给你一个整数 n，使得从 n 中删除 k 个数字之后的数字最大。

输入

输入一个整数 n (0 <= n <= 10^100)，和需要删除数字 k <= 100的个数

输出

输出删除k个数字之后的最大整数

样例输入

1432219 3

样例输出

4329

提示

无

来源

无

题目链接：最大数字 - C语言网

思路：

通过贪心的方法。 根据题意， 就是删除k个数字 保持原序列顺序不变的情况 下，使得 剩下的数字组成的最大。

我们一般比较一个数的大小，是怎么比的 ，比如 8999 9000 ，是不是先看最高位，

第一个数最高位为8 第二个数最高位为9，那么后面根本就不用关心。所以一个数大不大 由高位决定。

最高位相同，比次高位，依次类推。因此此题可以按以下步骤解决。

1.从最高位 开始找，找相邻的两个数中，高位的数字小于低位的数字，则应该把 高位的数字删掉，

2.如果是一个原序列是一个递减序列（或者 全为 11111 这种均匀序列），则删除最后一个元素就好了。

例如  1432219   要删除 3个  先通过 人工删除 肯定 删除 两个1 再删 一个2 就得到 最大数字， 4329。

分析一下 为什莫要这莫删，

首先 删去首位 的 1  因为 删掉 1  最高位 就可以由原来的 1 变为 4，由 1XXXXX,变成了4XXXXX。多划算 对吧。

现在变成 432219 ，4比3 大 当然不能删4 ，再比较3 和 2 当然也不能删，再看2和2 ，也不能删，看到 1 小于9 当然 删掉1.

然后变成了43229， 按步骤来 看到 2小于9 ，就应该 删掉2 。就变成了4329 同时也删掉了3个数。

AC代码：

#include<stdio.h> 
#include<string.h>
int main(){
	char n[102];int k,i,t,len;
	while(~scanf("%s%d",&n,&k)){
	     len=strlen(n);//获取字符串长度 
	   	   while(k--){
		     for(i=0;i<len-1;i++)if(n[i]<n[i+1])break; //从最高位开始找，找到到高位小于低位的 就跳出  
			 while(i+1<len)n[i]=n[i+1],i++;//通过移位覆盖法删掉应该移除的元素。（之后就相当于要移除最后一个元素） 
			 len--;//字符串长度减少 （若应该去除最后一个元素 ，直接 长度减少） 
		   } 
		n[len]=0;printf("%s\n",n);
       }
	return 0;
}

当然 还可以用链表，更容易 删除元素，同时 程序也更优，但是我还是喜欢 代码简洁的 哈哈哈

​