PAT A1038 Recover the Smallest Number

题目链接

解题思路

这个题目理解起来可能比较难，但是代码写起来简单！首先就是考虑要按字典序将这些字符串排序，但发现32,321,3214这些数前后位置不一样的话数字大小不确定。所以就要判断两个字符串数前后位置变化哪个更小！排序后将字符串拼接，并去掉前导零即可。

注意

sort函数的cmp非常强大！就是直接根据a+b<b+a来排序，这样每两个字符串数拼接后，最终都会比两个数交换位置后的数要小！

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn=1e4+10;
string nums[maxn];
int n;
bool cmp(string& a,string& b){//比较函数可以将每两个数进行比较，整体排序
    return a+b<b+a;
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<n;i++) cin>>nums[i];
    sort(nums,nums+n,cmp);
    string ans="";
    for(int i=0;i<n;i++){
        ans+=nums[i];
    }
    while(ans.length()!=0){
        if(ans[0]=='0'){
            ans.erase(ans.begin());
        }else{
            break;
        }
    }
    if(ans.length()==0){
        cout<<"0";
    }else{
        cout<<ans;
    }

    return 0;
}