ZeroJudge 解題筆記：a528. 大數排序

作者：王一哲
日期：2025年7月11日


ZeroJudge 題目連結：a528. 大數排序

解題想法

因為 Python 支援大數運算，可以直接排序。C++ 則要用字串格式，分成兩個字串 a、b 開頭都是 +，開頭都是 -，a 正 b 負、a 負 b 正，共 4 種狀況排序。

Python 程式碼

使用時間約為 22 ms，記憶體約為 3.4 MB，通過測試。

import sys

for line in sys.stdin:
    if not line.strip(): continue
    n = int(line)
    nums = sorted([int(sys.stdin.readline()) for _ in range(n)])
    result = [f"{num:d}\n" for num in nums]
    sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 396 kB，通過測試。

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

bool mycmp(const string& a, const string& b) {
    if (a[0] != '-' && b[0] != '-') {  // a, b 都是正的
        if (a.size() == b.size()) return a < b;  // 長度相等，按照字典排序，a < b
        return a.size() < b.size();  // 長度不相等，長的比較大，放後面
    } else if (a[0] != '-' && b[0] == '-') {  // a 正、b 負
        return false;  // a 放後面
    } else if (a[0] == '-' && b[0] != '-') {  // a 負、b 正
        return true;  // a 放前面
    } else {  // a, b 都是負的
        string aa = a.substr(1), bb = b.substr(1);  // 刪除開頭的負號
        if (aa.size() == bb.size()) return aa > bb;  // 長度相等，按照字典排序，aa > bb
        return aa.size() > bb.size();  // 長度不相等，長的比較小，放後面
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;
    while(cin >> n) {
        vector<string> nums (n);
        for(int i=0; i<n; i++) cin >> nums[i];
        sort(nums.begin(), nums.end(), mycmp);
        for(auto num : nums) cout << num << "\n";
    }
    return 0;
}