2025年7月11日 星期五

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;
}


沒有留言:

張貼留言