蓝桥杯 2019省赛 C/C++ A TH

知识点

并查集

题目¶

给定一个长度为 NN 的数组 A=[A1,A2,⋅⋅⋅AN]A=[A1,A2,···AN]，数组中有可能有重复出现的整数。

现在小明要按以下方法将其修改为没有重复整数的数组。

小明会依次修改 A2,A3,⋅⋅⋅,ANA2,A3,···,AN。

当修改 AiAi 时，小明会检查 AiAi 是否在 A1∼Ai−1A1∼Ai−1 中出现过。

如果出现过，则小明会给 AiAi 加上 11；如果新的 AiAi 仍在之前出现过，小明会持续给 AiAi 加 11，直到 AiAi 没有在 A1∼Ai−1A1∼Ai−1 中出现过。

当 ANAN 也经过上述修改之后，显然 AA 数组中就没有重复的整数了。

现在给定初始的 AA 数组，请你计算出最终的 AA 数组。

输入格式

第一行包含一个整数 NN。

第二行包含 NN 个整数 A1,A2,⋅⋅⋅,ANA1,A2,···,AN。

输出格式

输出 NN 个整数，依次是最终的 A1,A2,⋅⋅⋅,ANA1,A2,···,AN。

数据范围

1≤N≤1051≤N≤105,
1≤Ai≤1061≤Ai≤106

输入样例：

5
2 1 1 3 4

输出样例：

2 1 3 4 5

思路

考虑并查集，由于该A数据范围为11e6，可以初始化一个11e6的数组，数组元素为下标，即每棵树的根节点都是自身，处理输入数字，通过递归找到根节点，并修改数组内容+1，即指向后一棵树，

代码

#include <iostream>
using namespace std;
#define MAXN 1000100
int N;
int p[MAXN];

int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d\n", &N);

    for (int i = 1; i < MAXN; i++)
        p[i] = i;

    for (int i = 0; i < N; i++)
    {
        int t;
        scanf("%d", &t);
        t = find(t);
        printf("%d ", t);
        p[t] = t + 1;
    }

    return 0;
}

// 错误 超时
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int N;
set<int> s;

int main()
{
    scanf("%d", &N);
    int t;
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &t);
        while (s.find(t) != s.end())
            t++;
        s.insert(t);
        printf("%d ",t);
    }

    return 0;
}