题解：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;
}