删数问题

删数问题

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注