摘要
Title: A1038 Recover the Smallest Number (30)
Tag: 贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

A1038 Recover the Smallest Number (30)

题意

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.
给定一个数组，数组中包含若干个整数，数组中整数可能包含前导 0。你需要将数组中的所有数字拼接起来排成一个数，并使得该数字尽可能小。
思路

判断数字a, b拼凑成的数字ab还有哪个大，直接用拼接之后的字符串比较大小就可以
即如果字符串比较 $ab<ba$ ，则ab表示的数小于ba表示的数，注意是小于号，没有等于！！别管为啥了，cpm函数都这样

所以，如果也排成最大的数也是同理

另原理，一个集合如果能够排序，那么它一定是全序集，全序集需要满足三个性质：反对称性、传递性、完整性
本题可证明用 return a + b < b + a; 的方法，来达到题目所需的要求，并且能够证明以上三条性质

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-09 12:57:42
* @FilePath: \GPLT\A1038\A1038.cpp
* @LastEditTime: 2023-01-09 13:20:26
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    int n;
    cin >> n;
    vector<string> s(n);
    for (int i = 0; i < n; ++i)
        cin >> s[i];

    sort(ALL(s), [&](const string &a, const string &b) { return a + b < b + a; });

    string res;
    for (int i = 0; i < SZ(s); ++i)
        res += s[i];

    int i = 0;
    while (i < SZ(res) - 1 && res[i] == '0') // 去掉前导0的同时，一定要保留一位，也就是如果最后剩下0，也要保留
        ++i;
    cout << res.substr(i);

    return 0;
}

A1038 Recover the Smallest Number (30)

题意

思路

代码