[PAT-A 1038]Recover the Smallest Number

题目大意：
给出若干可能还有前导0的字符串，将它们按某个顺序拼接，使得生成的数最小

思路：
1）基本处理，将字符串按字典顺序从小到大排序。
2）精确调整：排序之后如果出现s1+s2<s2+s1的情况，将s1放在s2的前面，否则将s2放在s1的前面。
如样例中的{32,321}排序之后为{32,321},那么s1+s2=32321,而答案为32132
3）如果去除前导0的字符串后长度变为0，则输出0

贪心策略证明：
假设有数字串s1+s2+…sk-1+sk+…+sn,如果对于任意i，有sk+si<si+sk成立，即sk与其他数字串排列时，sk排在前面更优
那么显然sk+sk-1<sk-1+sk成立，所以s1+s2+…+sk+sk-1+…+sn<s1+s2…sk-1+sk+…sn成立
依次类推可以得到sk+s1+s2+…+sk-1+sk+1+…+sn，使得串的结果最小。

AC代码：

//PAT_A 1038
#include<cstdio>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
const int maxn = 10010;
string str[maxn];
bool cmp(string a, string b) {
	return a + b < b + a;
}
int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
	}
	sort(str, str + n, cmp);//排序字符串
	string ans;
	for (int i = 0; i < n; i++) {
		ans += str[i];
	}
	while (ans.size() != 0 && ans[0] == '0') {
		ans.erase(ans.begin());
	}//去除前导0
	if (ans.size() == 0)cout << 0;
	else cout << ans;
	return 0;
}