题解：P1012 [NOIP 1998 提高组] 拼数

· · 题解

题解：P1012 [NOIP 1998 提高组] 拼数

同步于：题解：P1012 [NOIP 1998 提高组] 拼数

感谢我们伟大的 cz 发布了该贴，让我有了题解可写。

思路

明显排序，但排序规则要改变。我们发现应让开头数字较大的往前放，若开头数字相同比较下一位，然后串联就是最优解，那么排序规则应为什么呢？

bool cmp(string a,string b){
  return a>b;
}

这种方法很好想到字典序，但在 a 的长度大于 b 的长度时会出错，使 a 一定大于 b，不可取。

这说明我们要让 a 与 b 的长度相等。

bool cmp(string a,string b){
  return (a+b)>(b+a);
}

很明显，a+b 的长度等于 b+a 的长度，又可以枚举 a 开头与 b 开头两种情况，一举两得！

最后把 a 与 b 串联起来：

string ans="";
for(int i=0;i<n;i++){
  ans+=a[i];
}

完成！

最后——

AC 代码

#include<bits/stdc++.h>
using namespace std;
const int N=21;
string a[N];
int n;
bool cmp(string a,string b)return (a+b)>(b+a);}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    string ans="";
    sort(a,a+n,cmp);
    for(int i=1;i<=n;i++) ans+=a[i];
    cout<<ans<<endl;
    return 0;
}

求赞 /kel