- 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;
- }
来源: http://www.bubuko.com/infodetail-3400103.html