NOIP1998 最大数

我已经沦落到这种题都要写解题报告了。

这题不难,但是有点“调整”思想的运用。唐文斌写的一篇论文《浅谈“调整”思想在信息学竞赛中的应用》我还没有来得及看,这里先mark一下。

核心算法在于,如果两个数字a和b相连,如果ab>baab>ba,a放在前面一定会比b放在前面好。这个我是知道的,所以我一开始就运用上了排序,但是没有想到这个核心比较并不是简单地比较数字的字典序,字典序在有前缀出现的时候是有问题的!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 25
using namespace std;
string s[N];
inline int cmp(string a,string b){
    return a+b>b+a;
}
int main(){
    int n,cur;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    sort(s,s+n,cmp);
    for(int i=0;i<n;i++){
        cout<<s[i];
    }
}
avatar
Kerry Su