洛谷 P1012 [NOIP1998 提高组] 拼数 题解

题目简述

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

题目分析

定义

• 设 $X$ 为数字 $x$ 的字符串形式。
• $A+B$ 表示字符串 $A$ 和字符串 $B$ 相连组成的字符串。

思路

既然要构造最优解，显然如果有不优的情况的话，就需要对序列进行调整，具体而言我们可以这样做：

如果有 $A_{i+1}+A_i>A_i+A_{i+1}$，其中 $1 \leq i \lt n$，那么就交换 $A_{i+1}$ 和 $A_i$，现在 $A$ 的字典序明显更大了。重复上述操作，直至没有满足上述条件的情况了。

证明

为什么上述做法是对的呢？我们可以考虑用反证法进行证明：

经过上述操作后，设最终序列为 $T_1 \dots T_n$，且序列 $T$ 满足 $T_{i}+T_{i+1} > T_{i+1}+T_i$，其中 $1 \leq i \lt n$。我们先假设命题不成立，则序列 $T$ 不是字典序最大的序列，而 $S$ 是字典序最大的序列，那么 $S$ 必然有与 $T$ 不同的地方，则必然有 $S_{i+1}+S_i>S_i+S_{i+1}$，此时如果交换 $S_i$ 和 $S_{i+1}$，则必然有更大的字典序，与假设矛盾，故命题成立。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define random(a,b) (rand()%(b-a+1)+a)
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
int n;
string s[21];
bool cmp(string a,string b)
{
	return a+b>b+a;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
	For(i,1,n)
	{
		cin>>s[i];
	} 
	sort(s+1,s+1+n,cmp);
	For(i,1,n)
	{
		cout<<s[i];
	}
	return 0;
}