題目

并查集解析

首先先讓所有的f（i）=i，即每個人最開始的祖先都是自己，然后就每一次都讓輪到那個數的父親+1（用過后的標記），第二次出現的時候就直接用父親替換掉

并查集的作用：并查集用于快速查找元素的根節點，并進行路徑壓縮以提高效率。

并查集適用場景

1.快速合并與查詢：需要頻繁合并集合（如標記某個數已被占用）和查詢根節點（找下一個可用位置）。
2.路徑壓縮優化：通過壓縮查找路徑，使得后續查詢接近常數時間復雜度。
3.動態維護連續區間：每個數字的父節點指向下一個可用位置，天然維護了一個動態遞增的區間。

代碼【并查集解】

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, f[100010];int find(int x) {if (f[x] == x)return x;return f[x] = find(f[x]);
}int main() {cin >> n;for (int i = 1; i <= 1e5; i++)f[i] = i;for (int i = 0; i < n; i++) {int x;cin >> x;x = find(x);cout << x << ' ';f[x] += 1;//為下一次重復做準備}return 0;
}

Set 解法解析

這道題我們可以利用set 的有序性和高效查找特性，直接找到每個元素的最小可用值。

代碼思路：
先將1~1e6的值依次存入set中，然后利用lower_bound()找到第一個大于等于x的值，使用過后再利用erase()刪除
【這個代碼的思路完全符合我們腦中所想】

lower_bound

是一個用于在有序序列中【有序序列set】查找特定元素的函數。它返回指向第一個不小于給定值的元素的迭代器。結合set（有序集合），可以高效解決需要動態維護有序數據并快速查找的問題。

lower_bound 的核心功能
1.作用：在有序序列中找到第一個不小于目標值的位置。
2.返回值：
i 如果存在符合條件的元素，返回指向該元素的迭代器。
ii如果所有元素都小于目標值，返回容器的end()迭代器。

在 set 中使用 lower_bound
set 的特性：
1.元素唯一且按升序自動排序。
2.插入、刪除和查找操作的時間復雜度為 O(log N)。
調用方式：

auto it = s.lower_bound(x);  // it 是迭代器，指向第一個 >=x 的元素
cout << *it;                 // *it 是該元素的實際值
s.erase(it);                 // 直接傳遞迭代器刪除元素（不需要 *）

lower_bound 下界 & upper_bound上界

為什么不用 vector 替代 set？
vector 的插入、刪除和查找效率較低，適合靜態數據。

vector 的查找必須遍歷或使用 find 算法，效率低。

代碼

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n;
set<int> s;int main() {cin >> n;for (int i = 1; i <= 1e6; i++)s.insert(i);for (int i = 0; i < n; i++) {int x;cin >> x;auto a = s.lower_bound(x); //lower_bound返回第一個大于等于x的值，在有序集合set中能完美解決該問題cout << *a << ' ';s.erase(a);}return 0;
}