大數比大小 題解

簡潔題意

給兩個最多 \(10^6\) 位、沒有前導零的非負整數字串 \(x\) 與 \(y\)，輸出 >、< 或 =。

解法

位數上看 \(10^6\)，long long 只到 \(19\) 位——連讀進來都做不到，所以整題只能在字串上操作。

沒有前導零這個保證是關鍵，它讓比較拆成兩層：

1. 先比位數：位數多的那個數一定比較大。\(10\) 只有兩位卻大於一位數的 \(9\)，就是這個道理。
2. 位數一樣多才比內容：從最高位往下找第一個不同的位，那一位大的數就比較大。

第 \(2\) 步其實就是字串的字典序比較（8.9）：兩個等長字串逐字元比第一個不同處，正是我們要的規則。所以位數相同時可以直接寫 x > y，不必自己寫迴圈。

常犯錯誤

1. 直接拿字串比大小，沒有先比位數。"9" > "10" 在字典序下成立，但 \(9 < 10\)。範例 1 會抓到這個錯。
2. 想先轉成 long long 再比。\(10^6\) 位的數字連 long long 的邊都摸不到。範例 2 會抓到這個錯。
3. 輸出多印空白或換行。本題用 identical 比對，輸出就是單獨一個字元加換行。

參考程式碼

#include <iostream>
#include <string>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string x, y;
    cin >> x >> y;

    // 沒有前導零時：位數多的比較大；位數一樣多就比字典序
    if (x.size() != y.size()) {
        cout << (x.size() > y.size() ? ">" : "<") << '\n';
    } else if (x == y) {
        cout << "=" << '\n';
    } else {
        cout << (x > y ? ">" : "<") << '\n';
    }
    return 0;
}

複雜度：\(O(|x| + |y|)\)。