1038 Recover the Smallest Number

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 (≤104) 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:

5 32 321 3214 0229 87

Sample Output:

22932132143287

 自定义排序函数：

当两个字符串不是一个是另一个的前缀这种情况时，直接按升序排序；

当一个是另一个的前缀时：取长度大的字符串前缀后的第一个字符（即当短的字符串长度为length时，取长字符串的s[length]）将它与短字符串的第一个字符对比，更小的放在前面；

这样可以保证每两个字符串之间的顺序一定是两种排列顺序中使组成的数更小的那个。

排序后按新的顺序组成答案字符串，注意去掉前导零，注意答案为0的情况。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string a[10010];

bool cmp(string s1, string s2) {
	int length = min(s1.size(), s2.size());
	for (int i = 0; i < length; i++) {
		if (s1[i] != s2[i]) {
			return s1 < s2;
		}
	}
	if (s1.size() < s2.size()) {
		if (s2[length] > s1[0]) {
			return true;
		} else {
			return false;
		}
	} else {
		if (s1[length] > s2[0]) {
			return false;
		} else {
			return true;
		}
	}
}

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n, cmp);
	bool flag = 0;
	string ans = "";
	for (int i = 0; i < n; i++) {
		ans += a[i];
	}
	for (int i = 0; i < ans.size(); i++) {
		if (ans[i] != '0') {
			flag = 1;
		}
		if (flag) {
			cout << ans[i];
		}
	}
	if (flag == 0) {
		cout << 0;
	}
	return 0;
}