Codeforces Round #315 Div2 B. Inventory 序列調整為排列最小修改

問題描述

給定長度 n（≤ 10⁵）的序列 a[i]（1 ≤ a[i] ≤ 10⁵）。需修改最少元素，使序列成為 1..n 的排列。輸出任意合法結果。

貪心策略

遍歷序列，維護 used[x] 標記值 x 是否已出現在結果中。
對於 a[i]：
- 若 1 ≤ a[i] ≤ n 且 !used[a[i]] → 保留，used[a[i]] = true
- 否則 → 標記需替換

收集所有未使用的 1..n 中的數字備用。再次遍歷，將需替換位置填入備用數字。

代碼實現

int a[100005], used[100005];
vector unused;

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    
    for (int i = 0; i < n; ++i) {
        if (1 <= a[i] && a[i] <= n && !used[a[i]]) used[a[i]] = 1;
        else a[i] = -1; // 標記需替換
    }
    
    for (int i = 1; i <= n; ++i)
        if (!used[i]) unused.push_back(i);
    
    int idx = 0;
    for (int i = 0; i < n; ++i)
        if (a[i] == -1) a[i] = unused[idx++];
    
    for (int i = 0; i < n; ++i)
        printf("%d%c", a[i], i==n-1?'\n':' ');
}

正確性證明

保留所有合法且未重複的值，替換其餘。因為合法值最多 n 個，未使用的合法值數量正好等於需替換位置數。任意填充順序均可構造排列。

複雜度

時間 O(n)，空間 O(n)。