修改数组【并查集维护集合的最大值、连续数字的最大值】

修改数组

题意

修改数组【并查集维护集合的最大值、连续数字的最大值】_第1张图片

思路

并查集蛮巧妙用法,暴力的话,加个st数组,每次用while判断就好了。

这个题实际上要求出:一段连续的数的最大值(这个数没有被使用过)

要是x被使用过,我们把这个f[X]=X+1,把x的父节点指向x+1。

将前面枚举过的元素用一个集合来表示,集合的根元素是集合所有元素的最大值.

代码

#include 

const int N = 1100010;

int p[N];

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

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

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

    return 0;
}


你可能感兴趣的