前言
这道题的题号于我比较有意义，于是就来写了。
思路
如果暴力枚举所有排列，时间复杂度为 \(O ( n ! )\)，显然不能通过本题。
考虑贪心的做法，特别地，若 \(1 \leq a_i \leq 9\)，直接从大到小排序即是最优。但对于 \(\forall a_i \in [1,10^9]\)，如果还是采用同样的策略，我们很容易举出反例：\(a_1 = 4 , a_2 = 15\)， 组合成 \(154\)，显然是不如 \(415\)。正解应当从高到低逐位考虑，比较到相同位置上的数更大的 \(a_i\) 排序在前，拼接起来就是最优解。
形式化地，对于最优解中的每一对相邻数字 \(A,B\)，都有 \(A + B \geq B + A\)，其中 \(A + B\) 表示 \(A,B\) 两个字符串的拼接。也就是说，对于最优解中 \(\forall i < j\)，都有 \(a_i \geq a_j\)。正确性也很好证明，假设在最优解中，存在相邻的两个数字 \(A\) 和 \(B\) 满足 \(A + B < B + A\)。那么交换 \(A\) 和 \(B\) 的位置，新的拼接结果会更大，这与"最优解"矛盾。
代码实现这里给出几种自定义 sort 比较函数的方法。
Code
传入自定义函数指针：
#include<iostream>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=21;
int n;
string num[N];
bool cmp(string x,string y)
{return x+y>y+x;
}
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++)cin>>num[i];sort(num+1,num+n+1,cmp);for(int i=1;i<=n;i++)cout<<num[i];return 0;
}
传入包含仿函数的对象：
#include<iostream>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=21;
int n;
string num[N];
class cmp
{public:bool operator()(string x,string y){return x+y>y+x;}
};
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++)cin>>num[i];sort(num+1,num+n+1,cmp());for(int i=1;i<=n;i++)cout<<num[i];return 0;
}
重载 < 运算符：
#include<iostream>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=21;
int n;
string num[N];
namespace std
{bool operator<(const string &x,const string &y){return (x+y).compare(y+x)>0;}
}
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++)cin>>num[i];sort(num+1,num+n+1);for(int i=1;i<=n;i++)cout<<num[i];return 0;
}
使用 Lambda 运算符：
#include<iostream>
#include<algorithm>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=21;
int n;
string num[N];
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++)cin>>num[i];sort(num+1,num+n+1,[](const string &x,const string &y){return x+y>y+x;});for(int i=1;i<=n;i++)cout<<num[i];return 0;
}
祝安好。