拼数

HEIMOFA / 2023-05-03 / 原文

拼数洛谷

题目描述

设有 \(n\) 个正整数 \(a_1 \dots a_n\)，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。

输入格式

第一行有一个整数，表示数字个数 \(n\)。

第二行有 \(n\) 个整数，表示给出的 \(n\) 个整数 \(a_i\)。

输出格式

一个正整数，表示最大的整数

样例输入

3
13 312 343

样例输出

34331213

提示

对于全部的测试点，保证 \(1 \leq n \leq 20\)，\(1 \leq a_i \leq 10^9\)。

先来一点符号规定

\(\overline{AB}\) 表示将 \(A\) 与 \(B\) 连接在一起所产生的字符串，如：\(A=123,B=456\) 则 \(\overline{AB}=123456\)
\(A->B\) 表示字符串 \(A\) 大于 \(B\)
\(A>B\) 表示 \(\overline{AB}->\overline{BA}\) ，也就是说 \(A\) 接在 \(B\) 前面比 \(B\) 接在 \(A\) 前面更优（其它符号，如 \(\le,\ge\) 亦如此）
\(\left\vert A \right\vert\)，表示 \(A\) 的长度

注意：

在不特殊说明的情况下，任何字母都表示字符串

这是一个贪心，先看代码，我再来解释

\(Code:\)

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=25;
string a[N];

bool cmp(string x,string y){
	return x+y>y+x;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) cout<<a[i];
	return 0;
}

这份代码说当每一个 \(a_i\) 与 \(a_{i+1}\) 满足 \(a_i>a_{i+1}\) 那么将数组输出出来便是答案

证明一下（证明为个人理解，可能并不严谨）

不难看出，当数组满足 \(a_1>a_2>a_3>...>a_n\) 时，此时依次输出便是答案

而我们知道，刚刚的那个排序保证了 \(a_1>a_2,a_2>a_3,a_3>a_4,...,a_n-1>a_n\)

现在需要证明的便成为了证明当 \(a_1>a_2\) 且 \(a_2>a_3\) 那么 \(a_1>a_3\) （也就是证明传递性）

首先要知道：当 \(A->B\) 时，肯定有\(\overline{AN}->\overline{BN}\) （反过来亦是如此）

这个很好证

首先根据不等式的性质，有 \(A\times 10^{\left\vert N \right\vert}+N->B\times 10^{\left\vert N \right\vert}+N\)

然后不就证出来了吗

回到原来的命题，便有 \(\overline{a_1a_3}->\overline{a_2a_3}\) ，\(\overline{a_2a_3}->\overline{a_3a_3}\)

根据不等式的传递性，有 \(\overline{a_1a_3}->\overline{a_3a_3}\)

再根据当 \(\overline{AN}->\overline{BN}\) 时，\(A->B\)