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

题目传送门

题意分析

容易发现，\(n\) 个数 \(a_1,a_2,a_3,\cdots,a_n\) 首尾相接，无论如何排列，最终得到的数 \(x\) 的位数是一定的。

那么当 \(x\) 的位数一定时，决定 \(x\) 的大小的便是 \(a_1,a_2,\cdots,a_n\) 的排列顺序。贪心的思路便是字典序尽可能地大。正确性是显然的。

注意不是越大的 \(a_i\) 就越前。例如 \(a=\langle13,2\rangle\)，取 \(132\) 是不优的。

因此可以写一个比较函数 cmp ，从最高位开始逐位比较两数该位大小，相同则比较下一位，否则该位较大的在前。

但是注意到数据范围比较小，因此有一种简便写法。利用 string 存储 \(a_i\)，比较 a 和 b 时：

• 若 a+b>b+a，则 a 在前。（a 在前会更大）
• 否则 b 在前。

有了比较函数，排一遍序即可。因为 \(n\leq20\)，什么排序都可以猴子排序除外。

AC 代码

//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
int n;
string a[21]; 
bool cmp(string a,string b){return a+b>b+a;
}
int main(){/*freopen("test.in","r",stdin);freopen("test.out","w",stdout);*/cin>>n;for(int i=1;i<=n;i++)cin>>a[i];sort(a+1,a+n+1,cmp);for(int i=1;i<=n;i++)cout<<a[i];/*fclose(stdin);fclose(stdout);*/return 0;
}