【甲級PAT】-1038 Recover the Smallest Number (30 分)-貪心

1038 Recover the Smallest Number (30 分)

題目

給出一組數字，求它們拼接後最小的數字

思路

對數字A和B，如果A+B的字典序比B+A小（這裡的“+”指字元換拼接，而不是算術加法），則将A排在前面，反之，将B排在後面。依照以上規則對數組進行排序。

然後對數組進行拼接。

最後去除前導零。如果去除後字元串為空，則輸出0。

#include <bits/stdc++.h>

using namespace std;

string a[10005];
bool cmp(string a,string b)
{
    return a+b<b+a;
}

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    sort(a,a+n,cmp);
    string ans;
    for(int i=0;i<n;i++)
        ans+=a[i];
    while(ans.size()>0&&ans[0]=='0')
        ans.erase(ans.begin());
    if(ans.length()>0)
        cout<<ans;
    else cout<<0;
    return 0;
}