删除数字求最小值

给定一个n位正整数a, 去掉其中k个数字后按原左右次序将组成一个新的正整数。对给定的a, k寻找一种方案,使得剩下的数字组成的新数最小。

提示：应用贪心算法设计求解

操作对象为n位正整数，有可能超过整数的范围，存储在数组a中，数组中每一个数组元素对应整数的一位数字。

在整数的位数固定的前提下，让高位的数字尽量小，整数的值就小。这就是所要选取的贪心策略。

每次删除一个数字，选择一个使剩下的数最小的数字作为删除对象。

当k=1时，对于n位数构成的数删除哪一位，使得剩下的数据最小。删除满足如下条件的a[i]：它是第一个a[i]>a[i+1]的数，如果不存在则删除a[n]。

当k>1（当然小于n），按上述操作一个一个删除。每删除一个数字后，后面的数字向前移位。删除一个达到最小后，再从头即从串首开始，删除第2个，依此分解为k次完成。

若删除不到k个后已无左边大于右边的降序或相等，则停止删除操作，打印剩下串的左边n−k个数字即可（相当于删除了若干个最右边的数字）。

代码如下：

#include "stdafx.h"
#include<stdio.h>
#include<iostream>

using namespace std;
const int num = 10;
int *delfmin(int n,int a[num],int k ){

    int i;
	int j;
	int t=n;
	if(k<=0){ return 0;}
	
	else{
		
		while(n!=t-k){
	for(i=1;i<=n;i++){
		
			if(a[i]>a[i+1]){
			
				for(j=i;j<=n-1;j++){	a[j]=a[j+1]; }
			    break;
                
			}
		}
	n--;
	}	
  }
	
	return a;

}

int main(int argc, char* argv[])
{
	int a[num];
	int n;
	int s;
	int k;
	int i,j;
	cout<<"输入数的位数：";
	cin>>n;
    cout<<endl<<"输入数的值：";
	cin>>s; 
    for(i = n;i>0;i--) //将数字的每一位存入数组中 
	{
		a[i] = s%10;
		s /= 10;
	}

	cout<<endl<<"输入要删除的个数：";
	cin>>k;
	delfmin(n,a,k);
    cout<<"删除后的最小值为：";
	for(i=1;i<=n-k;i++){
	
		cout<<a[i];
	}
	cout<<endl;
	return 0;
}

截图如下：