优先队列求前k极值

发表于 分类于 本文字数： 1.3k 阅读时长 ≈ 5 分钟
讲解一类用优先队列+拓展下一步极值的一类题

优先队列求前 k 极值

P2085 最小函数值 - 洛谷

暴力做法

由于 $1 \le A_i$,$0 \le B_i$,$0 \le C_i$, 可以发现: 当 (x) 增大时, 每个函数

$$F_i(x)=A_ix^2+B_ix+C_i$$

的函数值 单调递增.

所以, 可以暴力求出每一个函数的前 m 个值, 选出最小的 m 个.

由于 $1 \le n,m\le1e4$, 还有排序一类的操作, 这样并不稳妥.

正解

由于 $F_x<F_{x+1}$, 因此 每个函数在 $x=1$ 时取得最小值.
于是，所有函数的 $F_i(1)$ 一定包含了答案中的最小值.

接下来思考次小值可能来自哪里:

  • 可能来自其他函数的最小值 $F_j(1)$
  • 也可能来自当前最小值所在函数的下一个值 $F_i(2)$

这启发我们如下做法:

  1. 先把所有 $F_i(1)$ 放入一个小根堆.
  2. 每次从堆中取出当前最小值 $F_i(x)$, 加入答案.`
  3. 然后把同一函数的下一个值 $F_i(x+1)$ 再放入堆中。
  4. 重复上述过程 m 次即可。

由 $F_x<F_{x+1}$ 可知, 第 $x$ 取出来的数一定是第 $x$ 大的答案.

参考代码

完整代码

 
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
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
const int N = 1e4 + 4;
struct node {
    long long x;
    int fr, i;
    node(long long a, int b, int c) {
        x = a;
        fr = b;
        i = c;
    }
    bool operator<(const node& y) const { return x < y.x; }
    bool operator>(const node& y) const { return x > y.x; }
};
int a[N], b[N], c[N];
long long s(int i, int x) { return (long long)a[i] * x * x + b[i] * x + c[i]; }
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }
    priority_queue<node, vector<node>, greater<node>> p;
    for (int i = 1; i <= n; i++) {
        p.push(node(s(i, 1), i, 1));
    }
    for (int i = 1; i <= m; i++) {
        auto now = p.top();
        p.pop();
        cout << now.x << " ";
        p.push(node(s(now.fr, now.i + 1), now.fr, now.i + 1));
    }
    return 0;
}

P1631 序列合并 - 洛谷

与上一道题差不多.

先排序. 我们用 b[1] 分别与 a[i] 相加得到初始的值. 现在, 我们的优先队列有每一个 a[i] 贡献的最小值. 输出一个最小值 a[i]+b[j] 后, 再算 a[i]+b[j+1] 即可.

参考代码

完整代码

 
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
#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
using namespace std;
const int N = 1e5 + 5;
struct node {
    long long x;
    int fr, i;
    node(long long a, int b, int c) {
        x = a;
        fr = b;
        i = c;
    }
    bool operator<(const node& y) const { return x < y.x; }
    bool operator>(const node& y) const { return x > y.x; }
};
int a[N], b[N];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    priority_queue<node, vector<node>, greater<node>> p;
    for (int i = 1; i <= n; i++) {
        p.push(node(a[i] + b[1], i, 1));
    }
    for (int i = 1; i <= n; i++) {
        auto now = p.top();
        p.pop();
        cout << now.x << " ";
        p.push(node(a[now.fr] + b[now.i + 1], now.fr, now.i + 1));
    }
    return 0;
}

P5283 [十二省联考 2019] 异或粽子 - 洛谷

稍微有一些难度, 但整体思路差不多. 既然是 $l \sim r$ 一个区间, 不难想到用前缀和预处理. 求异或最大值, 当然要使用字典树了. 先对前缀异或和建立字典树, 在求出每一个前缀异或和值的最大异或值, 这也就是其作为一个端点所产生的最大值.

显然我们需要求次大值, 次次大值…这需要可持久化字典树, 但我显然不会. 考虑另外一种做法:

我们需要查找第 x 大的异或值. 对于每一个节点, 存储其子树中含有结束标记的数量. 分三种情况:

  1. Trie 里根本没有相反位的分支.
    那没得选, 只能走相同位. 这一位 XOR 结果是 0.
  2. 相反位的子树里至少有 rnk 个数
    说明第 rnk 大的结果就在这一堆里面.
    于是直接走相反位分支, 同时这一位 XOR 结果记为 1.
  3. 相反位子树里的数不足 rnk 个.
    说明所有这些更大的 XOR 已经被排在前面了.
    于是把它们全部跳过, 选择相同的子树.

这样子我们就实现了查找第 x 大的异或值, 按照原来的思路处理即可.

参考代码

完整代码

 
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
const int N = 20000010, NN = 500010;
typedef long long ll;
int tr[N][2], sz[N], num = 1;
void ins(ll x) {
    stack<int> s;
    for (int i = 0; i < 34; i++) {
        s.push((x >> i) & 1);
    }
    int now = 1;
    sz[now]++;
    while (!s.empty()) {
        x = s.top();
        s.pop();
        if (!tr[now][x]) {
            tr[now][x] = ++num;
        }
        now = tr[now][x];
        sz[now]++;
    }
}
ll ask(ll x, int rnk) {
    ll ans = 0;
    stack<int> s;
    for (int i = 0; i < 34; i++) {
        s.push((x >> i) & 1);
    }
    int now = 1;
    while (!s.empty()) {
        x = s.top();
        s.pop();
        ans <<= 1;
        if (!tr[now][x ^ 1]) {
            now = tr[now][x];
        } else if (sz[tr[now][x ^ 1]] >= rnk) {
            now = tr[now][x ^ 1];
            ans |= 1;
        } else {
            rnk -= sz[tr[now][x ^ 1]];
            now = tr[now][x];
        }
    }
    return ans;
}
ll s[NN];
struct node {
    int u, rnk;
    ll v;
    bool operator<(const node y) const { return v < y.v; }
};
int main() {
    int n, k;
    cin >> n >> k;
    ll x;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        s[i] = s[i - 1] ^ x;
    }
    for (int i = 0; i <= n; i++) {
        ins(s[i]);
    }
    priority_queue<node> p;
    for (int i = 0; i <= n; i++) {
        p.push((node){i, 1, ask(s[i], 1)});
    }
    ll ans = 0;
    for (int i = 1; i <= k * 2; i++) {
        auto now = p.top();
        p.pop();
        ans += now.v;
        if (now.rnk < n) p.push((node){now.u, now.rnk + 1, ask(s[now.u], now.rnk + 1)});
    }
    cout << ans / 2;
    return 0;
}