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

Solution

• 设 $a,b,c$ 分别为 $A,B,C$ 这三个字符串表示的数，$\lvert A\rvert$ 表示 $A$ 的长度。
• $A+B>B+A$ 等价于 $10^{\lvert B\rvert}+b>b\cdot10^{\lvert A\rvert}+a$，这也等价于 $\frac{a}{10^{\lvert A\rvert}-1}>\frac{b}{10^{\lvert B\rvert}-1}$。
• 那么我们知道 $\frac{a}{10^{\lvert A\rvert}-1}>\frac{b}{10^{\lvert B\rvert}-1}$，$\frac{b}{10^{\lvert B\rvert}-1}>\frac{c}{10^{\lvert C\rvert}-1}$，那么当然有 $\frac{a}{10^{\lvert A\rvert}-1}>\frac{c}{10^{\lvert C\rvert}-1}$，也就是说 $A$ 比 $C$ 优了。

Code

#include <bits/stdc++.h>
using namespace std;
string s[50];
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 >> s[i];
	sort(s + 1, s + 1 + n, cmp);
	for (int i = 1; i <= n; i ++)
		cout << s[i];
	return 0;
}