P1012 [NOIP1998 提高组] 拼数 【STL 字符串排序】

题目描述

设有 nn 个正整数 a_1 \dots a_na1​…an​,将它们联接成一排,相邻数字首尾相接,组成一个最大的整数。

输入格式

第一行有一个整数,表示数字个数 nn。

第二行有 nn 个整数,表示给出的 nn 个整数 a_iai​。

输出格式

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

输入输出样例

输入 #1复制

3
13 312 343

输出 #1复制

34331213

输入 #2复制

4
7 13 4 246

输出 #2复制

7424613

思路

题目是水题,但想迅速解出来,也是要技巧。这里用STL会非常简便,因为STL的string的字符串拼接可以处理本来很麻烦的比较大小,比如35和3524拼接,很明显353524会比352435大,如果用一个数字一个数字的比较来比较35和3524会很麻烦

我用了冒泡排序

#include <iostream>
#include <cstdio>
using namespace std;
int n;
const int N=25;
//char a[N][40];
string a[N];
int main()
{
  	cin>>n;
  	for(int i=0;i<n;i++)
    cin>>a[i];
  	for(int i=0;i<=n-1;i++)
  	{
  		for(int j=0;j<=n-i-1;j++)
  		{
  			if(a[j]+a[j+1]<a[j+1]+a[j])
  			swap(a[j],a[j+1]);
		}
	}
	for(int i=0;i<n;i++)
	cout<<a[i];
	cout<<endl;
	return 0;
} 

重点还是对string用法的熟练度,char a[][]也就等同于 string a[]

上一篇:STL_set容器


下一篇:STL 模板复习