[PAT解题报告] Recover the Smallest Number
经典题 给定一些整数，求合并把它们连接起来求最小的数。
其实要使得连接起来的数，最小我们把a和b连接起来，如果ab(连接）比ba小，则应该先a后b，所以问题就变成一个排序问题了，cmp函数就是连接后的数谁小……
连接可以用string的“+”操作。还有就是输出后注意首0去掉，而且如果全是0，应该输出0。
简单证明一下这个算法的正确性。
假设最后的解 连接顺序(字符串顺序）：
a[0] a[1] a[2] ...a[i] a[i + 1]....
那么这个数前面a[0]...a[i - 1]连接简单记录为X,后面部分简单记录为Y，并假设a[i], a[i ＋
1]是第一个违背我们规定顺序的相邻两个位置（如果不存在这样的位置，就是按照我们规定的顺序排好了……)，所以(a[i][a[i + 1])
> (a[i + 1]a[i])
则连接好的数是 X(a[i]a[i + 1])Y, 那我如果交换a[i], a[i + 1]，则形成的数X(a[i +
1][a[i])Y，显然会更小。位数没变，因为前后没变，中间部分变小了。
这样就证明了，最后一定没有(a[i][a[i + 1]) > (a[i + 1]a[i])这样的位置。
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
string s[10002];
char t[10];
bool cmp(const string &a,const string &b) {
return (a + b) < (b + a);
}
int main() {
int n;
scanf("%d",&n);
for (int i = 0; i < n; ++i) {
scanf("%s",t);
s[i] = t;
}
sort(s, s + n, cmp);
bool have = false;
for (int i = 0; i < n; ++i) {
int j = 0;
if (!have) {
for (; (j < s[i].length()) && (s[i][j] == '0'); ++j)
;
}
if (j < s[i].length()) {
have = true;
printf("%s",s[i].substr(j).c_str());
}
}
if (have) {
puts("");
}
else {
puts("0");
}
return 0;
}
原题链接：http://www.patest.cn/contests/pat-a-practise/1038
查看10道真题和解析