删数问题（贪心算法）

1.问题描述：

问题描述：给定n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数，对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。

对于给定的正整数a，编程计算删去k个数字后得到的最小数。

输入文件示例：

178543

4

输出文件示例：

13

2.相关算法：

#include<stdio.h>
#define M 6
int main(){
	int arr[]={1,7,8,5,4,3};
	int arrMark[]={0,0,0,0,0,0};//用作标记的数组，成员记为1表示删除，记为0表示未删除 
	int delNum;//要删除的个数 
	int i;
	int j;
	int next=0;//记录下一个未标记删除的下标 
	
	scanf("%d",&delNum);//输入要删除的数量 
	
	for(i=0;i<delNum;i++){
		for(j=0;j<M;j++){
			if(j==M-1) {//如果是最后一个元素，那么直接删除即可 
					arrMark[j]=1;
					break; 
			}
			while(next<=j||arrMark[next]==1){//找到下一个未标记删除的下标  
				next++;
			}
			if(arrMark[j]!=1&&arr[j]>arr[next]){//如果发现降序，则删除 
				arrMark[j]=1;
		    	break;
			}
		}
		next=0;
	}
	
	for(i=0;i<M;i++){//输入未标记删除的数组元素 
		if(arrMark[i]!=1)
			printf("%d",arr[i]);
	}
}

3.问题分析与解题思路：

数位越高,对数字最终的大小的影响会越大，因此最好删除数位比较高的数字。而且如果是相邻数字之间删除比较大的数字，最终的结果会比较小。因此我们可以从最高位开始找，找到第一个比自己下一位数字大的数字进行删除。每次都这样处理，最终就可以得到目标结果。