### 题目
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 different 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 (≤10^4^) 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. Notice that the first digit must not be zero.
**Sample Input:**
```cpp
5 32 321 3214 0229 87
```
**Sample Output:**
```cpp
22932132143287
```
### 题目解读
题目意思是 给出`n`个数字字符串,比如`"123","0789","32","321"`,找出这几个串拼接后形成的最小的数字,并且要去掉`前导零`
**思路:**
思路大家都能想到,就是把这些字**符串从小到大排序**,越小的越在前,这样直接拼接,就能得到最小的数字,最后去掉`前导0`。
**重点:排序用的比较函数如何写?**
```cpp
bool cmp(string s1, string s2) {
// 字符串比较
return s1 < s2;
}
```
这样写有什么问题?比如 `"32"` 会被认为 `小于` `"321"`,从而放在前面,导致最后拼接的串是 `32 321` ,但实际上 `32 321 > 321 32`(`321`放在前面)
所以,这个函数应该这样写
```cpp
bool cmp(string s1, string s2) {
// 字符串加法是拼接
return s1 + s2 < s2 + s1;
}
```
任意两个串组合只能得到两种组合结果,怎么样结果最小,就怎么样排序。
你可能还有个问题,如果某个字符串以0开始,它岂不是永远会被放在前面?比如`0789` 会被认为 `小于 123`,所以最后存储结果是 `0789 123`,但`0789`实际上是`789`,`789>321`,所以你有点觉得结果应该是 `321 0789`,嗯?是不是觉得有点不对了,`0789 123`还就是小于`321 0789`,所以,这样写是没错的。
**为啥呢**???? 以`0`开始的串,排在最前面,`0`会被当做`前导0`移除,相当于组合数少了一位,如果放在中间,`0`不能省略,相当于组合数长了一位,长了一位那肯定更大了啊
既然这么麻烦,我能不能把所有串输入后,都把`前导0`去了,这样就可以直接用第一种排序方法了??,当然不可以,你这不相当于破坏原来数字了,比如 `0123` 和`0456`,最终结果是`01230456->1230456`,你把两个`0`去了,成啥了 `123456`,这差了多少?
综上,比较函数只能这么写
```cpp
bool cmp(string s1, string s2) {
// 字符串加法是拼接
return s1 + s2 < s2 + s1;
}
```
去除`前导0`,这个比较好办,字符串全拼接在一起后,判断第一个字符,如果是`0`,就去除第一个字符。
```cpp
// 去除前导0
while(res[0] == '0') res.erase(res.begin());
```
这里我用的`erase()`方法,++注意这个函数只传一个参数(位置索引)的情况下,如果参数是个数字,那么它会把字符串从这个索引往后部分全部删除;如果传入是个迭代器,那么它移除的只是这个位置上的一个字符++。
**最后记得考虑一下特殊情况**
```cpp
// 排除特殊情况
if(res == "") cout << 0;
```
### 完整代码
```cpp
#include
#include
#include
using namespace std;
// 不能写成 return a < b
// 比如 "32" < "321",但是 32 321 > 321 32
bool cmp(string s1, string s2) {
// 字符串加法是拼接
return s1 + s2 < s2 + s1;
}
string str[10000];
int main() {
// n个数字串
int n;
cin >> n;
// 输入
for(int i = 0; i < n; i++)
cin >> str[i];
// 排序
sort(str, str + n);
// 拼接
string res = "";
for (int i = 0; i < n; ++i)
res += str[i];
// 去除前导0
while(res[0] == '0') res.erase(res.begin());
// 排除特殊情况
if(res == "") cout << 0;
cout << res;
return 0;
}
```

PAT 1038 Recover the Smallest Number (30分) string巧排序