课课通 P187最大整数 NOIP提高组1998拼数

 本人水平有限，题解不到为处，请多多谅解

 本蒟蒻谢谢大家观看

题目：传送门

题意如下：有n个正整数，将他们连在一起排成一排可以组成的一个最大的多位整数

 

输入样例：

3

13 312 343

输出样例：

34331213

法一：

 如果直接比较字符串大小会WA,为什么呢？

解释如下：有一个反例  ch1='31',ch2='312';按照直接比较大小的话，答案为：31231

实际上，答案为：31312；为什么会出现这种情况呢？请继续往下看：

我们正解应该为比较ch1+ch2与ch2+ch1；意思是比较连接字符串后字符大小；

令 temp1=ch1+ch2=31231  ,  temp2=ch2+ch1=31312  ; 

因为 temp1<temp2 即 strcmp(temp1,temp2)<0 就更新temp1;

若不理解以下代码，可观看博客：https://www.cnblogs.com/nlyzl/p/11267905.html

code ：

#include<bits/stdc++.h>
using namespace std;
char num[21][30],temp1[60],temp2[60];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
    }
    //cin>>temp1>>temp2;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            strcpy(temp1,num[i]);
            strcpy(temp2,num[j]);
            strcat(temp1,num[j]);
            strcat(temp2,num[i]);
            //cout<<" ans1= "<<temp1<<endl;
        //    cout<<" ans2= "<<temp2<<endl;
            if(strcmp(temp1,temp2)<0)
            {
                strcpy(temp1,num[i]);
                strcpy(num[i],num[j]);
                strcpy(num[j],temp1);
            }
            //cout<<" temp1= "<<temp1<<endl;
            //cout<<" temp2= "<<temp2<<endl;
        }
    }
    for(int i=1;i<=n;i++)
    cout<<num[i];
}

法二：

直接利用string 将其排好序最后直接输出

code：

#include<bits/stdc++.h>
using namespace std;
int n,yzl;
string a[100010],k,m,ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        cin>>a[i];
        //scanf("%s",a);
    }
    for(int i=1;i<=n;i++){
        yzl=0;
        for(int j=i+1;j<=n;j++){
            if(a[i]+a[j]<a[j]+a[i]){
                swap(a[i],a[j]);
//                k=a[i]+a[j];
//                m=a[j]+a[i];
//                yzl=k.compare(m);
//                if(yzl>0&&j==n&&i==1)ans=k;
//                else if(yzl<=0&&j==n&&i==1)ans=m;
                //cout<<"m= "<<m<<" k= "<<k<<" i ="<<i<<" j= "<<j<<endl;
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<a[i];
    //cout<<ans<<endl;
    //for(int i=1;i<=n;i++)cout<<a[i];//printf("%s",a);
    return 0;
}