把每个数出现后占掉这个位置，并查集维护“从某个值开始往后第一个没被占用的位置”，从而快速找到修改后的最小可行值。
OJ: luogu
题目 ID: P8686
难度:普及/提高-
标签:并查集模拟贪心
日期: 2026-06-20 00:15
题意
给定一个数组，从左到右依次处理每个数。
处理到 a[i] 时：
- 如果它之前没出现过，就保留
- 如果它之前出现过，就不断加
1 - 直到变成一个之前没有出现过的数为止
问最后整个数组会变成什么。
思路
先看一个小数据暴力：
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
set<int> used;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
while (used.count(a[i])) {
a[i]++;
}
used.insert(a[i]);
}
for (int i = 1; i <= n; i++) {
if (i > 1) {
cout << ' ';
}
cout << a[i];
}
cout << '\n';
return 0;
}暴力很直接：
- 用一个集合记录已经出现过的值
- 处理当前数时，只要它已经出现过，就不停
+1
这个思路容易理解，但如果重复很多次，可能会连续试很多个位置。
关键观察是：
- 当某个值
x已经被占用了，下一次再想放到x，我们真正关心的是“从x开始往后，第一个没被占用的位置在哪里”
这正是一个“后继并查集”模型。
我们把每个整数位置看成一个点：
- 如果
x还没被占用，那么find(x) = x - 如果
x已经被占用，就把它并到x+1 - 这样
find(x)就会一路跳到后面第一个可用位置
处理流程：
- 初始化
fa[x] = x - 处理当前值
a[i]时，令x = find(a[i]) - 把答案位置设成
x - 表示
x已经被占用，于是令fa[x] = find(x + 1)
这样每个位置一旦被占用，就会自动跳到下一个可用位置，避免反复试探。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int MAXV = 1200005;
int n;
int a[MAXN];
int fa[MAXV]; // fa[x] : 从 x 开始往后，第一个还没被占用的位置
void init_dsu() {
for (int i = 0; i < MAXV; i++) {
fa[i] = i;
}
}
int find_root(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_root(fa[x]);
return fa[x];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
init_dsu();
for (int i = 1; i <= n; i++) {
int x = find_root(a[i]);
a[i] = x;
// x 已经被占用，下一次如果还想用 x，就应该跳到 x+1 之后的可用位置。
fa[x] = find_root(x + 1);
}
for (int i = 1; i <= n; i++) {
if (i > 1) {
cout << ' ';
}
cout << a[i];
}
cout << '\n';
return 0;
}复杂度
设最终涉及的值域大小为
并查集路径压缩后，每次查询和修改的均摊复杂度近似常数，总复杂度为：
空间复杂度
总结
这题表面看是模拟加一，实际上核心是“快速找到某个值往后第一个没被占用的位置”。一旦把这个需求抽成后继并查集，代码就会很短。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
