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

  Custom sort function ：

When two strings are not prefixed by one and the other , Sort directly in ascending order ;

When one is the prefix of another ： Take the first character after the prefix of a long string （ That is, when the short string length is length when , Take the long string s[length]） Compare it with the first character of the short string , Put the smaller one in front ;

This ensures that the order between each two strings must be the smaller of the two permutations .

After sorting, the answer string is formed in a new order , Take care to remove leading zeros , Note that the answer is 0 The situation of .

#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;
}