PAT1038. Recover the Smallest Number

题目大意

1038. Recover the Smallest Number

给定 n 个数字片段, 求这个所能组成的最大数值是多少, 输出并忽略前导 0.

分析

不能简单的按照字典序排序, 因为有320, 32, 8 这种情况, 若简单按照字典序进行排序, 会出现 323208, 而真正的答案是 320328.

假设序列中有相邻的数字片段a, b. 若a, b交换位置能使 a + b < b + a (因为二者长度相同, 所以比较字典序即可) 则序列可以变小, 所以最终答案也是这个顺序, 给 sort 函数传一个 cmp 即可.

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool aFuckingAmazingCmp(const string& a, const string& b){
    return a + b < b + a;
}
int main(){
    int nNum;
    cin >> nNum;
    vector<string> arr;
    for(int i = 0; i < nNum; i++){
        string s;
        cin >> s;
        arr.push_back(s);
    }
    sort(arr.begin(), arr.end(), aFuckingAmazingCmp);
    string s = "";
    for(int i = 0; i < nNum; i++)
        s += arr[i];
    while(s.size() != 0 && s[0] == '0')
        s.erase(s.begin());
    if(s.size() == 0)
        cout << 0 << endl;
    else
        cout << s << endl;
    return 0;
}