洛谷P1012

题目描述

给定 \(n\) 个正整数 \(a_1 \dots a_n\)，将它们连接成一个最大的数。

分析

1. 先取其中两个数字 \(a\) 和 \(b\)，例如 \(12\) 和 \(121\)。
2. 有两种合并的结果，分别是 \(a+b\) 和 \(b+a\)，即 \(12121\) 和 \(12112\)。
3. 取较大的 \(a+b\) \((12121)\) 为拼接结果。
   猜测：由于拼接后的长度是一定的，当 \(n=2\) 时，只需要比较 \(a+b\) 的 \(b+a\) 然后取较大的那个就行了。能不能把这种思想扩展到 \(n>2\) 的情况呢？
   观察：

• 如果 \(a\) 应该排在 \(b\) 前面（\(a+b > b+a\)），
• 如果 \(b\) 应该排在 \(c\) 前面（ \(b+c > c+b\)），
• 那么 \(a\) 一定排在 \(c\) 前面（\(a+c > c+a\)）！
• 最终的顺序将是 \(a+b+c\) 。
  结论：这个比较规则满足传递性，考虑直接对它们排序。

Solution

标签：贪心

直接对这些数字字符串排序即可，排序规则如下：

(string x, string y) { 
return x + y > y + x; 
}

时间复杂度

总时间复杂度：\(O(n \log n \cdot L)\)

• 排序需要 \(O(n \log n)\) 次比较。
• 每次比较 \(O(L)\) （\(L\) 是字符串平均长度）。
• 由于 \(n \leq 20\)，\(L \leq 10\)（\(a_i \leq 10^9\)），可以接受。

参考代码

#include <bits/stdc++.h>
using namespace std;
string s[21];
int n;
int main() {cin >> n;for (int i = 1; i <= n; i++)cin >> s[i];sort(s + 1, s + 1 + n, [](string x, string y) { return x + y > y + x; });for (int i = 1; i <= n; i++)cout << s[i];return 0;
}