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

题目

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 (≤104) 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:

5 32 321 3214 0229 87

Sample Output:

22932132143287

题目解读

题目意思是 给出n个数字字符串,比如"123","0789","32","321",找出这几个串拼接后形成的最小的数字,并且要去掉前导零

思路:

思路大家都能想到,就是把这些字符串从小到大排序,越小的越在前,这样直接拼接,就能得到最小的数字,最后去掉前导0

重点:排序用的比较函数如何写?

bool cmp(string s1, string s2) {
	// 字符串比较
    return s1 < s2;
}

这样写有什么问题?比如 "32" 会被认为 小于 "321",从而放在前面,导致最后拼接的串是 32 321 ,但实际上 32 321 > 321 32321放在前面)

所以,这个函数应该这样写

bool cmp(string s1, string s2) {
    // 字符串加法是拼接
    return s1 + s2 < s2 + s1;
}

任意两个串组合只能得到两种组合结果,怎么样结果最小,就怎么样排序。

你可能还有个问题,如果某个字符串以0开始,它岂不是永远会被放在前面?比如0789 会被认为 小于 123,所以最后存储结果是 0789 123,但0789实际上是789789>321,所以你有点觉得结果应该是 321 0789,嗯?是不是觉得有点不对了,0789 123还就是小于321 0789,所以,这样写是没错的。

为啥呢???? 以0开始的串,排在最前面,0会被当做前导0移除,相当于组合数少了一位,如果放在中间,0不能省略,相当于组合数长了一位,长了一位那肯定更大了啊

既然这么麻烦,我能不能把所有串输入后,都把前导0去了,这样就可以直接用第一种排序方法了??,当然不可以,你这不相当于破坏原来数字了,比如 01230456,最终结果是01230456->1230456,你把两个0去了,成啥了 123456,这差了多少?

综上,比较函数只能这么写

bool cmp(string s1, string s2) {
    // 字符串加法是拼接
    return s1 + s2 < s2 + s1;
}

去除前导0,这个比较好办,字符串全拼接在一起后,判断第一个字符,如果是0,就去除第一个字符。

    // 去除前导0
    while(res[0] == '0') res.erase(res.begin());

这里我用的erase()方法,注意这个函数只传一个参数(位置索引)的情况下,如果参数是个数字,那么它会把字符串从这个索引往后部分全部删除;如果传入是个迭代器,那么它移除的只是这个位置上的一个字符

最后记得考虑一下特殊情况

    // 排除特殊情况
    if(res == "") cout << 0;

完整代码

#include <iostream>
#include <string>
#include <algorithm>
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;
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://vivi.run/archives/pat-1038-smallest-number