UVa 10905 Children's Game：自定義排序規則拼接最大數字

問題描述

給定一組數字，將它們拼接成一個盡可能大的整數。數字很大，需用字串處理。關鍵在於排序比較函數：不是字典序，而是比較 a+b vs b+a。

核心比較邏輯

bool cmp(const string &a, const string &b) {
    return (a + b) > (b + a); // 降序：較大的組合在前
}

例如 "9" > "81"，因為 "981" > "819"。

完整解法

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

bool cmp(const string &a, const string &b) {
    return a + b > b + a;
}

void ChildrenGame() {
    long long n;
    vector<string> vs;
    string s;
    while (cin >> n && n != 0) {
        vs.clear();
        for (long long i = 0; i < n; i++) {
            cin >> s;
            vs.push_back(s);
        }
        sort(vs.begin(), vs.end(), cmp);
        for (long long i = 0; i < vs.size(); i++)
            cout << vs[i];
        cout << endl;
    }
}

int main() {
    ChildrenGame();
    return 0;
}

關鍵點

• 使用 string 避免大數溢位
• 排序規則：a+b > b+a 確保拼接結果最大
• 輸入以 0 結束，多組測資
• 時間複雜度 O(n log n × L)，L 為字串長度