tanjin.cpp

贪婪算法 算法例题 有效的解决了数字删除的问题 让你可以从一串数字中选出一些最大的

#include <stdio.h>
int length(char n[])
{
	for (int i=1;i<100;i++)
		if (n[i]=='#')
			return i--;
}
void delete1(char n[],int b,int k)
{
	int i;
	for (i=b;i<=length(n)-k;i=i+1)
		n[i]=n[i+k];
}

void main()
{
	char n[100];
	int s,i,j,j1,c,data[100],len;
	for (i=1;i<100;i++)
	{
		scanf("%c",&n[i]);
		if (n[i]=='#')
			break;
	}
	printf("Please input how many number you want to delete :");
	scanf("%d",&s);
	len=length(n);
	if (s>len)
	{
		printf("error data");
		return;
	}
	j1=0;
	for (i=1;i<=s;i=i+1)
	{	
		for (j=1;j<100;j++)
			if (n[j]>n[j+1])
			{
				delete1(n,j,1);
				if (j>j1)
					data[i]=j+i-1;
				else 
					data[i]=data[i-1]-1;
				j1=j;
				break;
			}
		if (j>length(n))
				break;
	}
	for (c=i+1;c<=s;c++)
	{
		j=len-c+1;
		delete1(n,j,1);
		data[c]=j;

	}
	while (n[1]=='0'&&length(n)>1)
		delete1(n,1,1);
	for (i=1;i<len-s;i++)
		printf("%c",n[i]);
	printf("\n");
	for (i=1;i<=s;i++)
		printf("%d ",data[i]);
	

}