题意

n

个数，把它们打乱、首尾相接，求相接后拼成的数字的最大值。

分析

首先有一些前置芝士。

string 类型有 + 运算符，表示将两个字符串拼接；还可以用大于小于号比较两个字符串字典序的大小；
字典序的大小是这么规定的：
- 如果两个字符串长度不一样，那么在短的字符串后面补齐后，按字符串长度相同的方法计算；（没用……）
- 如果两个字符串长度一样，那么依次比较两个字符串的每个字符，两个字符的 ASCII 码相同则继续比较，否则 ASCII 码小的字符所在字符串字典序小。（重要！）

根据上面两条知识，如果我们把正整数存在 string 中，如果两个字符串长度相同，那么字典序的比较就相当于两个数字的比较。反之亦然，两个相同长度的数字比较相当于字符串的字典序比较。我们将其称作性质 1。

回到这道题。这道题是经典的临项微扰贪心，只要考虑相邻两个元素即可。为什么？这是因为当它们两个前面、后面都不变时，结果只与它们两个的顺序有关，而不与前面、后面有关，所以排序时只考虑相邻两个。

我们为了方便拼接，用字符串存数字。那么该按照什么规定排序呢？既然知道结果只与相邻两个字符串有关，那么为了让这个数字最大，必须要让这两个字符串拼接后的字典序尽量大（显然无论谁在前在后拼接长度相同，就用上性质 1 了）。既然只有左接右、右接左两种情况，两种情况拼起来、字典序一比就能得到最大解了。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define up(_name_,_leftbound_,_rightbound_) for(auto _name_=(_leftbound_);(_name_)<=(_rightbound_);++(_name_))
int n;
string s[25];
bool cmp(string s1,string s2){
	return (s1+s2)>(s2+s1);
}
int main(){
	cin>>n;
	up(i,1,n) cin>>s[i];
	sort(s+1,s+n+1,cmp);
	up(i,1,n) cout<<s[i];cout<<endl;
	return 0;
}
/*
---INFORMATIONS---
TIME:1145/1/4 11:45:14
PROBLEM:P1012
CODE BY __CrossBow_EXE__ Luogu uid967841
CEXE好闪，拜谢CEXE。
*/

题解：P1012 [NOIP 1998 提高组] 拼数

文章操作

题意

分析

代码

相关推荐

评论

题解：P1012 [NOIP 1998 提高组] 拼数