题目
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 diferent 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 (<=10000) 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. Do not output leading zeros.
Sample Input:
5 32 321 3214 0229 87
Sample Output:
22932132143287
题目分析
已知一系列数字段，顺序可以随意调换，求最后组合成的最小数字（打印需要去掉前导0）
解题思路
- 对所有数字段排序，排序技巧有技巧性（s1+s2<s2+s1，排序结束后所有s1,s2对都是取s1+s2，所以整个数组s1+s2...sk组合为最小数字）
该证明来自晴神笔记P163
- 将排序处理完的所有数字段拼接，擦除前导0（擦除技巧有技巧性）
易错点
- 特殊情况：所有数字段都为0，擦除前导0后，可能最终字符串为空，需要输出0
Code
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(string &s1,string &s2) {
return s1+s2<s2+s1;
}
int main(int argc, char * argv[]) {
int N;
scanf("%d",&N);
string ss[N];
for(int i=0; i<N; i++) cin>>ss[i];
// 排序
sort(ss,ss+N,cmp);
// 获取字符串结果
string rs;
for(int i=0; i<N; i++) rs+=ss[i];
// 擦除前导0
while(rs.length()!=0&&rs[0]=='0')rs.erase(rs.begin());
// 若rs都为0，擦除完后，长度为0；
if(rs.length()==0)printf("0");
else printf("%s",rs.c_str());
return 0;
}