NYOJ 448 寻找最大数 解题报告

寻找最大数

时间限制：1000ms |内存限制：65535KB

难度：2

描述

请在整数 n中删除m个数字,使得余下的数字按原次序组成的新数最大，

比如当n=92081346718538，m=10时，则新的最大数是9888

输入

第一行输入一个正整数T，表示有T组测试数据
每组测试数据占一行，每行有两个数n,m（n可能是一个很大的整数，但其位数不超过100位，并且保证数据首位非0，m小于整数n的位数）

输出

每组测试数据的输出占一行，输出剩余的数字按原次序组成的最大新数

样例输入

2

92081346718538 10

1008908 5

样例输出

9888

98

题目连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=448

之前训练时，遇见过一道名为《删数》的题目，差别就是那个让求最小的数，这个让找最大的数。

由于只能从给定的数字中删掉确定数目的数字，每位数字之间不允许交换，所以先考虑最大数字的特点，即尽量让大数在高位。

给定数字为一个N位数，删掉其中M位（M<=N），使得到的（N-M）位数的值尽可能大。其实也就是从一个N位数中取出（N-M）个数，使得到的数尽量大。

按照上述的两个思想，就是说，取每一位数时，从给定数中都要取最大的数。这样，取数的过程中保证每一位都是最大，这样结果也必然是最大的。

下面举例说明：

从source_number：105789中删去3位数，所得数字放在result_num中。

先从source_number取得result_num的第一位（按从左往右记数）。

数位： 1 2 3 4 5 6

Source_num：1 0 5 7 8 9

第一步：取得7，之后source_num变为89。只能从source_num的前4位（length_source –fetch_num + 1，length_source为源数的长度，fetch_num为取数的个数）中取，这样不会导致取数之后，剩余的数字不够取的情况。

第二步：取得8，source_num变为9。

第三步：取得9，结束。

Result_num为：789。

不难发现，取数的过程是递归的，即每次都是取最大的那个数，所以用递归写程序较简单。

下面两种写法的思想是相同的，只是实现方法不同。

递归写法：

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

char number[105];
char result[105];

void fetch(char num[], int fetch_num, int count)
{
	int i, max, length;
	if (fetch_num == 0)
	{
		result[count] = '\0';
		return ;
	}
	else
	{
		length = strlen(num);
		max = 0;
		for (i = 1; i < length - fetch_num + 1; ++i)
		{
			if (num[i] > num[max])
			{
				max = i;
			}
		}
		result[count++] = num[max];
		fetch(num + max + 1, fetch_num - 1, count);
	}
}

int main()
{
	int test_num, del_num, length;
	scanf("%d", &test_num);
	while (test_num--)
	{
		scanf("%s %d", number, &del_num);
		length = strlen(number);
		fetch(number, length - del_num, 0);
		printf("%s\n", result);
	}
	return 0;
}

非递归：

#include <cstdio>
#include <iostream>
#include <cstring>

using namespace std;

char number[105];
char result[105];

int main()
{
	int i, test_num, del_num, length, start, max, count, fetch_num;
	scanf("%d", &test_num);
	while (test_num--)
	{
		scanf("%s %d", number, &del_num);
		length = strlen(number);
		fetch_num = length - del_num;
		start = 0;
		count = 0;
		while (fetch_num--)
		{
			max = start;
			for (i = start + 1; i < length - fetch_num; ++i)
			{
				if (number[i] > number[max])
				{
					max = i;
				}
			}
			result[count++] = number[max];
			start = max + 1;
		}
		result[count] = '\0';
		printf("%s\n", result);
	}
	return 0;
}