HBC16625[NOIP1998 ]冒泡排序 [NOIP1998 提高组] 拼数

题库丰富多样，涵盖各个领域，全网最全C++题库，让您在练习中不断成长！

问题分析：

1. 很容易想到的，直接将数据存储在一个列表中，再对字符串按照字典序逆序排列，再将列表中的字符串连接起来，就能获得最大的整数。写出代码，发现不能通过。

2. 仔细查看发现这样做是有问题的，例如321，32 。如果按照字符串字典序逆序排列，应该是321，32 。但很显然正确的排序应该是32，321 。这样拼出的数是更大的。

3. 所以我们可以自定义一个比较函数，让序列按照拼出的数比较大的顺序排列。

拟定计划：

1. 先用一个列表来存储数据

2. 定义一个比较函数

3. 通过这个比较函数对列表进行排序

#include<iostream>
using namespace std; 
string s[30],temp;
int i,j,suma;
void msort(int n)  //冒泡排序 
{
    for(i=1; i<n; i++){
        bool flag=true;
        for(j=1; j<=n-i; j++){
            if(s[j]+s[j+1]<s[j+1]+s[j]){  //字符串拼接后较大在前 
                temp=s[j],s[j]=s[j+1],s[j+1]=temp;
                flag=false;
            }
        }if(flag) break;
    }
}
int main(){
    int n;    
    cin>>n;
    for(i=1; i<=n; i++){  //输入 
        cin>>s[i];
    }
    msort(n);
    for(i=1; i<=n; i++){  //输出 
        cout<<s[i];
    } 
    
    return 0;
}

成为编程大师，不再是梦想！全网最全C++题库，助您开启编程新篇章。

标签： NOIP