【甲级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;
}