题目描述

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

输入格式

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

第二行有 n 个整数，表示给出的 n 个整数 。

输出格式

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

输入输出样例

输入 #1

3
13 312 343

输出 #1

34331213

输入 #2

4
7 13 4 246

输出 #2

7424613

说明/提示

对于全部的测试点，保证，。

题解

思路分析

数字收尾相接可以认为是字符串相加，故题意为有 nn 个字符串，首尾相接形成了一个新字符串，求新字符串字典序最大值。

做法

• 搜索（部分分） 暴力全排列搜索所有字符串的顺序，比较大小，得出最终答案。

• 贪心（满分）

对贪心正确性的证明：
分析可见两同样长字符串 若​ 比 ​ 大，必有 x 使得s1在 x 位第一次比大 。

说明只要前面的位大，就可以忽略后面的位，可以使用贪心解决，把对字典序贡献最大的放在前面。比较方法只要比较  和​ 的大小即可。

如：2 和 19 ，比较 2 和 19 哪个放在前面使字典序最大，也就是即比较 219 和 192 哪个大，因为 219 比 192 大，所以把 2 放在 19 前面

使用比较函数 cmp 后 sort 将字符串输出可得答案

bool cmp(string a,string b){return a>b;
}

代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
bool cmp(string a,string b){return a+b>b+a;
}int main(){int n;cin >> n;string a[n];for (int i = 0;i<n;i++) cin >> a[i];sort(a,a+n,cmp);for (int i = 0;i<n;i++){cout << a[i];}cout << endl;return 0;
}