题目

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given { 32, 321, 3214, 0229, 87 }, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

Input Specification:

Each input file contains one test case. Each case gives a positive integer $N$ ( $\le 10^4$ ) followed by $N$ number segments. Each segment contains a non- negative integer of no more than 8 digits. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print the smallest number in one line. Notice that the first digit must not be zero.

Sample Input:

1

5 32 321 3214 0229 87

Sample Output:

1

22932132143287

思路

这是一道数学题，如果找到简单的思路，代码可以很少。

交换两个数字字符串，比较可以得到一个最小的数字。在一个多于两个数字段组成的大数字中，这种局部的关系可以扩展至全部，即保证任意相邻的数字段组成的局部最小，就能使得整个数字达到最小。

可以反证：局部排好序后，如果任意相邻的两个数字段互换得到更小的结果，就违反了局部已达到最小的前提条件。

比较方法：网上几乎全是比较a+b和b+a。我用的稍有不同，是将一个数字段自我重复，即123扩展为123123123123123，在相互比较，结果是一样的。这样有一个好处，就是传递性很好证明，a>b,b>c一定有a>c。

思路：

使用上述方法利用qsort排序。

输出时注意前面不能有0，需要防备各种意想不到的情况，请尝试以下输入：

1

3 0 00 0010

看看输出的是不是10

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void *a, const void *b)
{
	char *A = (char*)a, *B = (char*)b;
	char s1[17], s2[17];
	int lenA = strlen(A), lenB = strlen(B);

	/* Repeat the numbers to form a long string
	 * e.g. 123 -> 123123123123123 */
	for (int i = 0; i < 16 / lenA; i++)
		strcpy(s1 + i * lenA, A);
	for (int i = 0; i < 16 / lenB; i++)
		strcpy(s2 + i * lenB, B);

	return strcmp(s1, s2);
}

int main()
{
	int N, k = 0, number = 0;
	char numbers[10000][9] = {{0}};

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%s", numbers[i]);

	qsort(numbers, N, 9 * sizeof(char), cmp);

	/* Go to the first non-zero segment */
	while (k < N && number == 0)
		sscanf(numbers[k++], "%d", &number);

	/* Print the first non-zero segment */
	printf("%d", number);
	/* Print the rest */
	while (k < N)
		printf("%s", numbers[k++]);
	return 0;
}