[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