藍橋杯真題：錯誤票據——尋找斷號與重號 ID

題目背景

某單位發放連續編號票據，錄入時發生一處錯誤：導致某 ID 缺失（斷號），另一 ID 重複（重號）。輸入 N 行雜亂 ID，找出斷號與重號（斷號不在最大/最小值）。

解題關鍵

1. 輸入處理：行內/行末可能有多餘空格，需逐字符解析整數
2. 所有 ID 収集後排序
3. 遍歷排序數組：

• 若 a[i] == a[i-1] → 重號 = a[i]
• 若 a[i] > a[i-1] + 1 → 斷號 = a[i] - 1

輸入解析技巧

char line[10010];
int nums[100010], cnt = 0;
for (int i = 0; i < N; ++i) {
    gets(line);
    int len = strlen(line), val = 0;
    for (int j = 0; j <= len; ++j) {
        if (j < len && isdigit(line[j])) 
            val = val * 10 + line[j] - '0';
        else if (val > 0) 
            nums[cnt++] = val, val = 0;
    }
}

完整流程

1. 讀 N，循環讀 N 行
2. 解析所有整數存入數組
3. 排序數組
4. 單次遍歷找出斷號與重號
5. 先輸出斷號，再輸出重號

樣例驗證

輸入：5 6 8 11 9 / 10 12 9 → 排序後 5 6 8 9 9 10 11 12 → 斷號 7，重號 9。

複雜度

時間 O(T log T)，T 為總 ID 數（≤10000）；空間 O(T)。