题解|拼数

由于题目链接无法解析，我直接截图

这个题目要求根据所给数字拼接一个最大的数字

那怎么样的数字最大呢？

假设给定 543 和 654，有两种拼接方式：

654 543 和 543 654，这里 654543 更大，显然我们可以看出来，要使得拼接后的数字越大，我们就要让单一位越大的数字占据越高位。

那么思路就清晰了：

我们判断两个大数的优先级可以创建两个栈，分别记录两个大数的各位数字，从高到低依次进行比较，大的在前，小的在后。

这个时候遇到一个情况：假设有 654 和 654 X ，怎么分辨优先级？

这个时候分情况，如果 X＞6（假设 X=8），那么 6548 654>654 6548

如果 X＜6（假设 X=3），那么 654 6543>6543 654

也就是说，我们需要判断剩余位数字和二者首位的大小进行优先级判定。

整体代码如下：

#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
using namespace std;
void a(int *nums,int n);
bool b(int a,int b);
int main(){
    int n=0;
    cin>>n;
    int nums[21];
    for(int i=0;i<n;i++) cin>>nums[i];
    
    a(nums,n);
    for(int i=0;i<n;i++) cout<<nums[i];
    return 0;
}
void a(int *nums,int n){
    for(int i=0;i<n;i++){	//这里采用冒泡排序进行排序
        for(int j=0;j<n-1-i;j++){
            if(!b(nums[j],nums[j+1])) swap(nums[j],nums[j+1]);
        }
    }
}

bool b(int a,int b){
    stack<int> A,B;
    while(a){
        A.push(a%10);
        a/=10;
    }
    while(b){
        B.push(b%10);
        b/=10;
    }
    
    int temp=A.top();	//存储首位数字
    while(!A.empty()&&!B.empty()){	//依次出栈，进行比较
        if(A.top()>B.top()) return true;
        else if(A.top()<B.top()) return false;
        else{
            A.pop();
            B.pop();
        }
    }
    //剩余位数字和首位数字进行比较
    if(!A.empty()) return (temp>A.top())?false:true;
    return (temp>B.top())?true:false;
}