[NOIP1998 提高组] 拼数
题目描述
设有
n
n
n 个正整数
a
1
…
a
n
a_1 dots a_n
a1…an，将它们联接成一排，相邻数字首尾相接，组成一个最大的整数。服务器托管网
输入格式
第一行有一个整数，表示数字个数
n
n
n。
第二行有
n
n
n 个整数，表示给出的
n
n
n 个整数
i
a_i
ai。
输出格式
一个正整数，表示最大的整数
样例 #1
样例输入 #1
3
13 312 343
样例输出 #1
34331213
样例 #2
样例输入 #2
4
7 13 4 246
样例输出 #2
7424613
提示
对于全部的测试点，保证
1
≤
n
≤
20
1 leq n leq 20
1≤n≤20，
1
≤
a
i
≤
1
0
9
1 leq a_i leq 10^9
1≤ai≤109。
思路
比较函数 cmp 用于确保拼接后的数值最大。
当用下面这个函数直接比较 x 和 y 的字典序时，虽然能通过大部分样例，但是仍有少量测试点 WA。
bool cmp(string x, string y)
{
return x > y;
}
为什么会这样呢？
举个例子：当有 32、321 这两个数字。
-
如果用
x > y比较，即先比较再拼接，则 321 > 32，拼接后为 32132，但是显然 32132 -
如果用
x + y > y + x比较，即先拼接再比较，则 32321 > 32132，正确。
所以，对于两个字符串 x 和 y，如果 x+y 的字典序大于 y+x 的字典序，则认为 x 大于 y。得到比较函数 cmp 如下。
bool cmp(string x, string y)
{
return x + y > y + x;
}
AC代码
#include
#include
#include
#include
#define AUTHOR "HEX9CF"
using namespace std;
const int N = 107;
int n;
string s[N];
bool cmp(string x, string y)
{
return x + y > y + x;
}
int main()
{
cin >> n;
for (int i = 1; i n; i++)
{
cin >> s[i];
}
sort(s + 1, s + n + 1, cmp);
for (int i = 1; i n; i++)
{
cout s[i];
}
cout endl;
return 0;
}
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: JDK11升级JDK17最全实践干货来了 | 京东云技术团队
1、前言 上篇文章给大家带来了JDK8升级JDK11的最全实践，相信大家阅读后已经对JDK11有了比较深入的了解。2021年9月14日，Oracle发布了可以长期支持的JDK17版本，那么从JDK11到JDK17，到底带来了哪些特性呢？亚毫秒级的ZGC效果到底…
