PAT 甲級 A1038 Recover the Smallest Number (30 分)

題目傳送門

本來很久沒寫部落格了，今天刷這道題真的氣死我了。。。

題目很簡單，題意：

給出若幹可能有前導0的數字串，将他們按某個順序拼接，使生成的數最小。
           

一開始我寫了好半天寫出來以下代碼：

#include "bits/stdc++.h"
using namespace std;
bool cmp(string a, string b){
    int index =0; char fir;
    bool flag = false;
    while (index<a.length()&&index<b.length()&&a[index]==b[index]){
        fir = a[0];
        index++;
        flag = true;
    }
    if (flag) {
        if (a.length()>b.length()) return a[index]<fir;
        else if (b.length()>a.length()) return b[index]<fir;
    }else{
        return a<b;
    }
}
int main(){
    int n;scanf("%d",&n);
    string ans[10005];
    for (int i = 0; i < n; ++i) {
        cin>>ans[i];
    }
    sort(ans,ans+n,cmp);
    for (int i = 0; i < n; ++i) {
        if(i==0) {
            int index;
            for (int j = 0; j < ans[i].length(); ++j) {
                if (ans[i][j] != '0') {
                    index = j;
                    break;
                }
            }
            ans[i] = ans[i].substr(index, ans[i].length() - index);
            cout<<ans[i];
        }
        else for (int j = 0; j < ans[i].length(); ++j) {
            cout<<ans[i][j];
        }
    }
}
           

能過題目給的樣例很開心了，但是一送出

到這裡還不氣，以為邏輯錯了很多。 直到到看到睛神的代碼：

#include "bits/stdc++.h"
using namespace std;
bool cmp(string a,string b){
    return a+b>b+a;
}
int main(){
    int n;cin>>n;
    string str[100010];
    for (int i = 0; i < n; ++i) {
        cin>>str[i];
    }
    sort(str,str+n,cmp);
    string ans;
    for (int i = 0; i < n; ++i) {
        ans+=str[i];
    }
    while (ans.size()!=0&&ans[0]=='0'){
        ans.erase(ans.begin());
    }
    if (ans.size()==0)cout<<0;
    else cout<<ans;
}
           

意識到自己真的是愚蠢，cmp直接一句話a+b>b+a就好了啊，完全是自己腦殘，連最簡單的字元串拼接都沒想到。。。。

看不懂頭檔案的同學戳這裡