删数问题

删数问题

时间： 1ms        内存：64M

描述：

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

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

输入：

输入数据的第1 行是1 个正整数a。第2 行是正整数k。

输出：

将计算出的最小数输出。

示例输入：

178543
4

示例输出：

13

提示：

参考答案（内存最优[752]）：

//第六届复赛 二
#include <stdio.h>
#include <memory.h>
#include <string.h>

//#define N 4
//char str[100]="92081346718538";
char str[105];
int vis[105];
int n;


int select(int t,char str[],int res){
	int i,len=strlen(str);
	int ma=0;
	for(i=1;str[i]!=0;i++){
		if(str[i]<str[ma] && len-i>=res)//>
			ma=i;
	}
	vis[t+ma]=1;
	return t+ma+1;
}

int main(){
	int i,len,k=0,flag=0;
	//char c=' ';
	gets(str);
	scanf("%d",&n);
	len=strlen(str);
	memset(vis,0,sizeof(vis));
	for(i=0;i<len-n;i++)
		k=select(k,&str[k],len-n-i);
/*	printf("先后被删除的数是：");
	for(i=0;str[i];i++){
		if(vis[i]==0){
			printf("%c%c",c,str[i]);
			c=',';
		}
	}
	printf("\n");
	printf("删除后所得的最大数是：");*/
	for(i=0;str[i];i++){
		if(vis[i]){
			if(str[i]!='0')
				flag=1;
			if(flag==0 && str[i]=='0')
				continue;
			printf("%c",str[i]);
		}
	}
	printf("\n");
	
	return 0;
}

参考答案（时间最优[0]）：

//第六届复赛 二
#include <stdio.h>
#include <memory.h>
#include <string.h>

//#define N 4
//char str[100]="92081346718538";
char str[105];
int vis[105];
int n;


int select(int t,char str[],int res){
	int i,len=strlen(str);
	int ma=0;
	for(i=1;str[i]!=0;i++){
		if(str[i]<str[ma] && len-i>=res)//>
			ma=i;
	}
	vis[t+ma]=1;
	return t+ma+1;
}

int main(){
	int i,len,k=0,flag=0;
	//char c=' ';
	gets(str);
	scanf("%d",&n);
	len=strlen(str);
	memset(vis,0,sizeof(vis));
	for(i=0;i<len-n;i++)
		k=select(k,&str[k],len-n-i);
/*	printf("先后被删除的数是：");
	for(i=0;str[i];i++){
		if(vis[i]==0){
			printf("%c%c",c,str[i]);
			c=',';
		}
	}
	printf("\n");
	printf("删除后所得的最大数是：");*/
	for(i=0;str[i];i++){
		if(vis[i]){
			if(str[i]!='0')
				flag=1;
			if(flag==0 && str[i]=='0')
				continue;
			printf("%c",str[i]);
		}
	}
	printf("\n");
	
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。