xxyQwQ
0%

【题解】ACMOJ 1125 合并优先队列

发表于 分类于

题目描述

ACMOJ - 1125 - 合并优先队列

初始共有 $n$ 个数各成一组，设计一个算法支持以下操作：

  • 将第 $x$ 组和第 $y$ 组合并
  • 删除并输出第 $x$ 组中最小的数
  • 向第 $x$ 组中加入一个数 $y$

保证初始个数 $n\leq 3\times 10^5$，操作次数 $m\leq 3\times 10^5$

问题分析

我们构造 $n$ 个优先队列，直接模拟即可，对于合并操作，只要将第 $y$ 组中的元素依次弹出，插入到第 $x$ 组中即可。这种解法的复杂度高达 $O(nm\log n)$，但是由于测试数据的随机性，不会发生最坏情况

事实上，我们只需稍作修改，利用启发式合并的方法，每次合并将较小的队列合并到较大的队列中，这样可以保证每次合并的均摊复杂度为 $O(\log n)$，总复杂度为 $O\left ((n+m)\log ^2 n\right )$

一些细节

务必保证优先队列实现的正确性，且预分配空间不要过大，否则可能会内存超限

代码

这里只给出朴素算法直接模拟的代码，启发式合并读者可以自行实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <cstdio>
#include <cctype>
#include <cstdarg>
#include <queue>
const int NMAX = 300005;

std::priority_queue<int, std::vector<int>, std::greater<int>> q[NMAX];
int n, m;

template <typename T>
void read(T &value)
{
    T result = T(0);
    bool sign = false;
    char word = getchar();
    while (!isdigit(word))
        sign |= (word == '-'), word = getchar();
    while (isdigit(word))
        result = result * 10 + T(word - '0'), word = getchar();
    value = sign ? -result : result;
}

template <typename T, typename... Ts>
void read(T &value, Ts &...remain)
{
    read(value);
    read(remain...);
}

int main()
{
    read(n, m);
    for (int i = 0, x; i < n; i++)
        read(x), q[i].push(x);
    for (int i = 0, x, a, b; i < m; i++)
    {
        read(x);
        if (x == 0)
        {
            read(a, b);
            while (!q[b].empty())
                q[a].push(q[b].top()), q[b].pop();
        }
        else if (x == 1)
        {
            read(a);
            if (q[a].empty())
                printf("-1\n");
            else
                printf("%d\n", q[a].top()), q[a].pop();
        }
        else if (x == 2)
        {
            read(a, b);
            q[a].push(b);
        }
    }
    return 0;
}