1038 Recover the Smallest Number

题目

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

分析

本题如果能够想到正确的贪心算法就很简单，不然就不容易做对。一开始是先将所有数据用int读入自动去0，然后发现这样会去掉很多不应该去掉的0，比如1 10 -> 101这样的情况。然后就直接按照string读入，在cmp的时候，按照每一位的大小来排序，位数不够则循环补上。但是还有测试点无法通过，最后查看题解，方法非常巧妙，直接用a+b和b+a进行比较，仔细一想好像就是我的cmp函数的简化表达版。。我以为我到了第三层，结果题解在第五层。代码也很简单，直接贴一下好了。

代码

//
// Created by masterCai on 2020/5/22.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

//bool cmp(string &a, string &b){
//    int s1=a.size(), s2=b.size();
//    int pos = 0;
//    for (pos = 0; pos < s1 && pos < s2; ++pos) {
//        if (a[pos] != b[pos]){
//            return a[pos] < b[pos];
//        }
//    }
//    if(pos < s1){
//        int i = 0;
//        while (i<s2 && pos < s1){
//            if(a[pos] != b[i]){
//                return a[pos] < b[i];
//            }
//            i += 1;
//            pos += 1;
//        }
//    } else{
//        int i = 0;
//        while (i<s1 && pos < s2){
//            if(a[i] != b[pos]){
//                return a[i] < b[pos];
//            }
//            i += 1;
//            pos += 1;
//        }
//    }
//    return a<b;
//}

bool cmp(string &a, string &b){
    return a+b<b+a;
}

int main(){
    int N;
    cin >> N;
    vector<string> a(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), cmp);
    string ans;
    for (int i = 0; i < N; ++i) {
        ans += a[i];
    }
    while (!ans.empty() && ans[0] == '0'){
        ans.erase(ans.begin());
    }
    if(ans.empty()){
        cout << 0;
    } else{
        cout << ans;
    }
    return 0;
}