P1012 [NOIP 1998 提高组] 拼数

题意简述

给定 $n$ 个正整数，将它们首尾相接，求能组成的最大整数。

解题思路

定义字符串集合 $S$ 上的二元关系 $\succ$：

$$x\succ y\iff\overline{xy}>\overline{yx}$$

其中 $\overline{xy}$ 表示字符串 $x$ 和 $y$ 的拼接。

设 $v(s)$ 为字符串 $s$ 对应的数值，$l(s)$ 为 $s$ 的长度。构造映射 $\varphi:S\to\mathbb{R}$：

$$\varphi(s)=\frac{v(s)}{10^{l(s)}-1}$$ $$\begin{aligned} x\succ y & \iff v(x)10^{l(y)}+v(y)>v(y)10^{l(x)}+v(x) \\ & \iff v(x)\left(10^{l(y)}-1\right)>v(y)\left(10^{l(x)}-1\right) \\ & \iff\frac{v(x)}{10^{l(x)}-1}>\frac{v(y)}{10^{l(y)}-1} \\ & \iff\varphi(x)>\varphi(y) \end{aligned}$$

由实数域上 $>$ 的传递性和非对称性，可知 $\succ$ 在 $S$ 上满足 严格弱序。

假设最优排列 $P$ 存在相邻逆序 $p_{i+1}\succ p_i$，交换两者得到 $P'$。

由于 $\overline{p_{i+1}p_i}>\overline{p_ip_{i+1}}$，且交换不影响前后缀的数值贡献。故 $P'$ 总数值严格增大，与 $P$ 为最优解矛盾。

因此，最优解为按 $\succ$ 降序的排列。

时间复杂度为 $O(n\log n)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<string> a(n);
	for(auto &s:a)cin>>s;
	sort(a.begin(),a.end(),[](auto x,auto y){return x+y>y+x;});
	for(auto s:a)cout<<s;
	return 0;
}