PAT 甲级 1038. Recover the Smallest Number (30) C++版

Posted on Edited on In

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 (<=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

将给出的数字片段合成一个最小的数字，这里很巧妙的运用了排序，将他们按照从小到大排序然后合成就可以了，这个排序参考我家票票的代码：https://www.liuchuo.net/archives/2303

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>

using namespace std;

int cmp(const void *a, const void *b) {
    string arg1 = *static_cast<const string *>(a);
    string arg2 = *static_cast<const string *>(b);

    if (arg1 + arg2 > arg2 + arg1) return 1;
    if (arg1 + arg2 < arg2 + arg1) return -1;
    return 0;
}

int main() {
    int n = 0;
    cin >> n;
    string *num = new string[n];
    for (int i = 0; i < n; i++) {
        cin >> num[i];
    }

    qsort(num, n, sizeof(num[0]), cmp);
    string ans;
    for (int i = 0; i < n; i++) {
        ans += num[i];
    }
    while (ans.length() != 0 && ans[0] == '0') {
        ans.erase(ans.begin());
    }
    if (ans.size() == 0) {
        cout << "0";
    } else {
        cout << ans;
    }
    delete[] num;
    return 0;
}