Codeforces 34C Page Numbers：區間合併輸出頁碼範圍

問題描述

輸入一個逗號分隔的頁碼序列（如 1,2,3,1,1,2,6,6,2），去重、排序，將連續區間合併為 l-r 格式，單頁輸出 l。輸出如 1-3,6。

核心算法：排序去重 + 線性掃描合併區間

1. 解析輸入字符串，提取整數存入陣列/向量。
2. 排序 + unique 去重。
3. 線性掃描：維護當前區間起點 l，若下一數 == 當前數+1 則延伸區間，否則輸出當前區間（l==r 輸出 l，否則 l-r），更新 l 為下一數。

關鍵代碼 (C++)

int main() {
    string s; getline(cin, s);
    vector a;
    // 解析逗號分隔整數
    stringstream ss(s);
    string token;
    while (getline(ss, token, ',')) a.push_back(stoi(token));

    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());

    int n = a.size();
    int l = a[0];
    for (int i=1; i<=n; ++i) {
        if (i == n || a[i] != a[i-1] + 1) {
            // 輸出區間 [l, a[i-1]]
            if (l == a[i-1]) printf("%d", l);
            else printf("%d-%d", l, a[i-1]);
            if (i != n) printf(",");
            if (i != n) l = a[i];
        }
    }
    puts("");
    return 0;
}

複雜度分析

• 時間：O(k log k) — k 為頁碼數量 (≤100)。
• 空間：O(k)。

關鍵點

• 輸入解析：getline + stringstream 按逗號分割。
• 去重：sort + unique + erase 標準三連擊。
• 區間輸出邏輯：i==n 作為哨兵強制輸出最後一區間。

總結

Codeforces 34C 是區間合併的入門題。核心是「排序去重 → 線性掃描檢測連續性 → 格式化輸出」。同類技巧用於「合併區間、匯總連續數據範圍」等場景。