贪婪算法之删数问题
给定n位正整数a，去掉其中任意k≤n 个数字后，剩下的数字按原次序排列组成一个新的正整数。
对于给定的n位正整数a 和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案。
Input 50267539
4
Output
239
本题可用贪婪算法(Greedy)快速解决。
代码如下：
#include<stdlib.h>
#include<string.h>
int main()
{
int num = 0;
int n;
char str[100];
int a[100];
scanf(“%d”,&num); //数字
scanf(“%d”,&n); //个数
itoa(num, str, 10); //转换为字符串
int flag=0; //是否是递增序列
int i;
int length=strlen(str); //长度
int x=length-n;
while(length!=x)
{
flag=0; //递增
for(i=0;i<length-1;i++)
{
if((str[i]-’0′)>(str[i+1]-’0′)) //比后一个数大 删掉
{
for(int temp=i;temp<length-1;temp++)
{
str[temp]=str[temp+1]; //覆盖
}
length-;
flag=1; //非递增
}
}
if(flag==0)
{
length-;//递增序列 删除最后一个
}
}
int tempFlag=0;
if(str[0]==’0′)
tempFlag=1; //首位为0 不应输出
for(int i=0;i<length;i++)
{
if(tempFlag==1)
tempFlag=0;
else
printf(“%c”,str[i]);
}
system(“pause”);
}
