设有n个正整数（n ≤ 20），将它们联接成一排，组成一个最大的多位整数。 例如：n=3时，3个整数13，312，343联接成的最大整数为：34331213 又如：n=4时，4个整数7，13，4，246联接成的最大整数为：7424613

易错点

直接按数值大小排序无法得到最优解：

  • 7 > 4，但 74 > 47
  • 312 > 13，但 31213 < 13312（需考虑连接顺序）
  • 343 > 312，但 343312 > 312343（正确顺序）

关键在于：两个数 a 和 b 的连接顺序应由 ab 和 ba 的数值大小决定，而非 a 和 b 的单独大小。

为什么简单排序无效？
  • 数值大小陷阱：7 < 13，但 713 > 137
  • 位数影响：312 和 13，312 > 13，但 13312 > 31213
  • 前缀干扰：343 和 312，343 > 312，且 343312 > 312343

因此，我们需要将数字转化为字符串，通过自定义cmp函数来实现得到最大的数

关键观察：
对于任意两个数 a 和 b，若 a ⊕ b > b ⊕ a，则 a 应排在 b 前面。
这个规则具有传递性（在无前导零的数字字符串下）：

  • 若 a⊕b > b⊕a 且 b⊕c > c⊕b，则 a⊕c > c⊕a
  • 证明：设 a,b,c 为字符串，比较 (a+b) > (b+a) 和 (b+c) > (c+b)
    通过数学变换（考虑字符串重复扩展）可证传递性成立
3. 算法正确性证明

贪心选择性质：
若存在最优解中相邻两元素 a,b 满足 a⊕b < b⊕a，则交换 a,b 可得到更大结果，与最优性矛盾。

最优子结构：
移除序列首元素后，剩余子序列仍需满足相同排序规则。

因此，全局最优解 = 每对相邻元素局部最优的序列

完整算法设计

步骤
  1. 输入处理：读取所有整数作为字符串（避免大数问题）
  2. 自定义排序：
    • 比较函数：bool cmp(a, b) { return a+b > b+a; }
    • 降序排列：使连接结果最大化
  3. 结果拼接：按排序顺序连接所有字符串
  4. 边界处理：题目限定正整数，无需处理全零情况
排序规则详解
比较对 a+b b+a 结果 顺序
"7","13" "713" "137" 713 > 137 7,13
"13","4" "134" "413" 134 < 413 4,13
"312","13" "31213" "13312" 31213<13312 13,312

最终序列：7 → 4 → 246 → 13 → "7424613"

代码实现

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;


bool customCompare(const string& a, const string& b) {
    // 直接拼接比较：避免数值溢出，使用字符串字典序
    // 由于无前导零，字典序等价于数值序
    return a + b > b + a;
}

int main() {
    int n;
    cin >> n;
    
    // 存储数字字符串（直接读入避免转换）
    vector<string> numbers(n);
    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
    }

    // 使用自定义规则排序
    sort(numbers.begin(), numbers.end(), customCompare);
    
    // 拼接排序后的字符串
    string result;
    for (const string& num : numbers) {
        result += num;
    }
    
    // 输出最终结果
    cout << result << endl;
    
    return 0;
}

常见错误分析

  1. 按数值排序：sort(nums.rbegin(), nums.rend()) → 在 [7,13] 失效
  2. 按字典序排序：sort(..., greater<string>()) → 在 [343,312] 失效（特别注意）

扩展思考

  1. 含零情况： 
    // 排序后检查是否全零
if (!result.empty() && result[0] == '0') 
    cout << "0" << endl;
  2. 自定义数据类型：若需处理超大整数（>1000位），可优化比较函数避免实际拼接： 
    bool customCompare(const string& a, const string& b) {
    int i = 0, j = 0;
    while (i < a.size() || j < b.size()) {
        char ca = (i < a.size()) ? a[i] : b[j % b.size()];
        char cb = (j < b.size()) ? b[j] : a[i % a.size()];
        if (ca != cb) return ca > cb;
        i++; j++;
    }
    return false; // 相等
}

复杂度分析

  • 时间复杂度：
    • 排序：O(n log n) 次比较
    • 单次比较：O(k)（k 为字符串平均长度）
    • 总计：O(n log n × k) = O(20 × log₂20 × 10) ≈ 200 次操作
  • 空间复杂度：
    • 存储字符串：O(n × k)
    • 结果字符串：O(n × k)
    • 总计：O(n × k) ≤ 20 × 10 = 200 字节

总结

本题通过自定义字符串排序规则（a+b > b+a）解决了连接顺序问题，核心在于：

  1. 将数值比较转化为字符串拼接比较
  2. 利用贪心策略保证每对相邻元素局部最优