1321：【例6.3】删数问题(Noip1994)

1321：【例6.3】删数问题(Noip1994)

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 25868     通过数: 9164

【题目描述】

输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

输出新的正整数。（n不超过240位）

输入数据均不需判错。

【输入】

n

s

【输出】

最后剩下的最小数。

【输入样例】

175438
4

【输出样例】

13

【算法分析】

贪心。循环s次，删掉s个大数，剩下的就是最小值。

【AC代码】

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=340;
char n[N];
int s,len,m,x;
signed main()
{
	scanf("%s%d",&n,&s);
	x=len=strlen(n);
	for(int i=1;i<=s;i++)
	{
		for(int j=0;j<len-1;j++)
			if(n[j]>n[j+1])//如果当前数大于下一个数
			{
				for(int k=j;k<len-1;k++)n[k]=n[k+1];//删掉那个数
				break;//跳出循环
			}
		len--;//长度-1
	}
	while(n[m]=='0' and x>1)m++,x--;//去除前导0
	for(int i=m;i<len;i++)printf("%c",n[i]);
	return 0;
}

给个关注吧

 

时间限制: 1000 ms         内存限制: 65536 KB
提交数: 25868     通过数: 9164

【题目描述】

输入一个高精度的正整数n，去掉其中任意s个数字后剩下的数字按原左右次序组成一个新的正整数。编程对给定的n和s，寻找一种方案使得剩下的数字组成的新数最小。

输出新的正整数。（n不超过240位）

输入数据均不需判错。

【输入】

n

s

【输出】

最后剩下的最小数。

【输入样例】

175438
4

【输出样例】

13

【算法分析】

贪心。循环s次，删掉s个大数，剩下的就是最小值。

【AC代码】

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=340;
char n[N];
int s,len,m,x;
signed main()
{
	scanf("%s%d",&n,&s);
	x=len=strlen(n);
	for(int i=1;i<=s;i++)
	{
		for(int j=0;j<len-1;j++)
			if(n[j]>n[j+1])//如果当前数大于下一个数
			{
				for(int k=j;k<len-1;k++)n[k]=n[k+1];//删掉那个数
				break;//跳出循环
			}
		len--;//长度-1
	}
	while(n[m]=='0' and x>1)m++,x--;//去除前导0
	for(int i=m;i<len;i++)printf("%c",n[i]);
	return 0;
}

给个关注吧