"蔚来杯"2022牛客暑期多校训练营3 C题

英文题面： NIO was the king of the OIN Kingdom.

He had NN children and wanted to teach them how to count. In the OIN Kingdom, pental is used in counting, so his children can only use 0, 1, 2, 3, and 4 to represent a number.

One day, NIO asked his children to write down their favorite numbers. After that, he came out with a problem: if he concatenated these numbers into a big number, what is the smallest number he could get? However, this problem was too hard for him to solve, so can you help him?

中文题面：

NIO是OIN王国的国王。

他有ññ孩子们，想教他们如何数数。在OIN王国里，pental是用来计数的，所以他的孩子们只能用0、1、2、3、4来代表一个数字。

有一天，蔚来让他的孩子们写下他们最喜欢的数字。之后，他提出了一个问题：如果他将这些数字串联成一个大数，他能得到的最小数字是多少？不过，这个问题对他来说太难解决了，你能帮帮他吗？

题解：

根据题意我们只需要求字典序最小的串即可，即我们排序的时候可以：

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

排序完输出即可,时间复杂度O(nlogn)。

#include<bits/stdc++.h>
using namespace std;
bool cmp(string &a, string &b)
{
    return a + b < b + a;
}
string a[2000100];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n, cmp);
    for (int i = 0; i < n; ++i) cout << a[i];
    return 0;
}