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

感谢我们伟大的 cz 发布了该贴，让我有了题解可写。

思路

明显排序，但排序规则要改变。我们发现应让开头数字较大的往前放，若开头数字相同比较下一位，然后串联就是最优解，那么排序规则应为什么呢？

CPP

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

这种方法很好想到字典序，但在

a

的长度大于

b

的长度时会出错，使

a

一定大于

b

，不可取。

这说明我们要让 $a$ 与 $b$ 的长度相等。

CPP

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

很明显，

a+b

的长度等于

b+a

的长度，又可以枚举

a

开头与

b

开头两种情况，一举两得！

最后把

a

与

b

串联起来：

CPP

string ans="";
for(int i=0;i<n;i++){
  ans+=a[i];
}

完成！

最后——

AC 代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=21;
string a[N];
int n;
bool cmp(string a,string b){
	return (a+b)>(b+a);
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	string ans="";
	sort(a,a+n,cmp);
	for(int i=0;i<n;i++){
		ans+=a[i];
	}
	cout<<ans<<endl;
	return 0;
}

~~无耻求赞qwq~~

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

文章操作

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

思路

AC 代码

相关推荐

评论

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