日期: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;
}
沒有留言:
張貼留言