ZeroJudge 解題筆記：c669. missing and duplicate

作者：王一哲
日期：2025年8月21日


ZeroJudge 題目連結：c669. missing and duplicate

解題想法

先讀取數列，將數列由小到大排序，取最小值 $imin$、最大值 $imax$、項數 $n$，等差數列加總理論值 $$ theory = \frac{(imin + imax) \times n}{2} $$ 如果實際上的數列加總為 $isum$，兩者相減 $$ diff = theory - isum = 缺少的項 - 重複的項 $$ 再用 set 刪除數列中重複的項，計算 set 的加總 $sum(uni)$，重複的項 $$ dup = isum - sum(uni) $$ 最後可以得到缺少的項 $$ mis = diff + dup $$

Python 程式碼

使用時間約為 26 ms，記憶體約為 3.4 MB，通過測試。

T = int(input())
for _ in range(T):
    arr = sorted(list(map(int, input().split())))  # 排序後的數列
    imin, imax, n = arr[0], arr[-1], len(arr)  # 最小值、最大值、數量
    isum = sum(arr)  # arr 的加總
    theory = (imin + imax) * n // 2  # 理論上的等差數量加總
    diff = theory - isum  # arr 加總與理論值的差
    uni = set(arr)  # 刪除重複的數字
    dup = isum - sum(uni)  # 重複的數字
    mis = dup + diff  # 遺失的數字
    print(mis, dup)

C++ 程式碼

使用時間約為 6 ms，記憶體約為 572 kB，通過測試。

#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int T; cin >> T; cin.ignore();  // 忽略行末的 \n
    string s;  // 暫存一行資料的字串
    stringstream ss;  // 暫存資料的容器
    set<int> uni;  // 不重複的數字
    while(T--) {
        int a, imin = 1E9, imax = 0, n = 0, isum = 0, unisum = 0;  // 變數、最小值、最大值、數量、加總、不重複的加總
        uni.clear();  // 清除 uni 的資料
        ss.clear();  // 清除 ss 的資料
        getline(cin, s); ss << s;  // 讀取一行字串，資料存入 ss
        while(ss >> s) {  // 從 ss 讀取資料
            a = stoi(s);  // s 轉成 int 存入 a
            if (a < imin) imin = a;  // 更新 imin
            if (a > imax) imax = a;  // 更新 imax
            n++;  // 更新 n
            isum += a;  // 更新 isum
            if (uni.count(a) == 0) {  // 如果 a 不在 uni 之中
                uni.insert(a); unisum += a;  // 更新 uni, unisum
            }
        }
        int theory = (imin + imax) * n / 2;  // 理論上的等差數量加總
        int diff = theory - isum;  // arr 加總與理論值的差
        int dup = isum - unisum;  // 重複的數字
        int mis = dup + diff;  // 遺失的數字
        cout << mis << " " << dup << "\n";
    }
    return 0;
}