题解：洛谷 P1801 黑匣子

【题目来源】

洛谷：P1801 黑匣子 - 洛谷

【题目描述】

Black Box 是一种原始的数据库。它可以储存一个整数数组，还有一个特别的变量 \(i\)。最开始的时候 Black Box 是空的．而 \(i=0\)。这个 Black Box 要处理一串命令。

命令只有两种：

• ADD(x)：把 \(x\) 元素放进 Black Box;
• GET：\(i\) 加 \(1\)，然后输出 Black Box 中第 \(i\) 小的数。

记住：第 \(i\) 小的数，就是 Black Box 里的数的按从小到大的顺序排序后的第 \(i\) 个元素。

我们来演示一下一个有11个命令的命令串。（如下表所示）

序号	操作	\(i\)	数据库	输出
1	ADD(3)	\(0\)	\(3\)	/
2	GET	\(1\)	\(3\)	\(3\)
3	ADD(1)	\(1\)	\(1,3\)	/
4	GET	\(2\)	\(1,3\)	\(3\)
5	ADD(-4)	\(2\)	\(-4,1,3\)	/
6	ADD(2)	\(2\)	\(-4,1,2,3\)	/
7	ADD(8)	\(2\)	\(-4,1,2,3,8\)	/
8	ADD(-1000)	\(2\)	\(-1000,-4,1,2,3,8\)	/
9	GET	\(3\)	\(-1000,-4,1,2,3,8\)	\(1\)
10	GET	\(4\)	\(-1000,-4,1,2,3,8\)	\(2\)
11	ADD(2)	\(4\)	\(-1000,-4,1,2,2,3,8\)	/

现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 \(m\) 个，GET 命令共有 \(n\) 个。现在用两个整数数组来表示命令串：

1. \(a_1,a_2,\cdots,a_m\)：一串将要被放进 Black Box 的元素。例如上面的例子中 \(a=[3,1,-4,2,8,-1000,2]\)。
2. \(u_1,u_2,\cdots,u_n\)：表示第 \(u_i\) 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 \(u=[1,2,6,6]\) 。输入数据不用判错。

【输入】

第一行两个整数 \(m\) 和 \(n\)，表示元素的个数和 GET 命令的个数。

第二行共 \(m\) 个整数，从左至右第 \(i\) 个整数为 \(a_i\)，用空格隔开。

第三行共 \(n\) 个整数，从左至右第 \(i\) 个整数为 \(u_i\)，用空格隔开。

【输出】

输出 Black Box 根据命令串所得出的输出串，一个数字一行。

【输入样例】

7 4
3 1 -4 2 8 -1000 2
1 2 6 6

【输出样例】

3
3
1
2

【算法标签】

《洛谷 P1801 黑匣子》 #线段树# #平衡树# #堆# #NOI导刊# #O2优化#

【代码详解】

// 部分分解法
#include <bits/stdc++.h>
using namespace std;const int N = 200005;  // 数组最大容量
int n, m, a[N], b[N], top = 1;  // n: 序列长度，m: 查询次数，a: 输入序列，b: 查询位置，top: 当前查询索引
multiset<int> mt;  // 可重复有序集合，用于维护当前元素
multiset<int>::iterator it;  // 集合迭代器int main()
{cin >> n >> m;  // 读入序列长度和查询次数// 读入序列afor (int i = 1; i <= n; i++){cin >> a[i];}// 读入查询位置bfor (int i = 1; i <= m; i++){cin >> b[i];}// 遍历序列afor (int i = 1; i <= n; i++){mt.insert(a[i]);  // 将当前元素插入multiset// 检查是否有查询位置等于当前索引iwhile (b[top] == i){// 找到第top小的元素it = mt.begin();  // 从最小的元素开始for (int j = 0; j < top - 1; j++){it++;  // 移动迭代器到第top小的元素}cout << *it << endl;  // 输出第top小的元素top++;  // 处理下一个查询}}return 0;
}

// 满分解法
#include <bits/stdc++.h>
using namespace std;const int N = 200005;  // 数组最大容量
int n, m, a[N], b[N], top = 1;  // n: 序列长度，m: 查询次数，a: 输入序列，b: 查询位置，top: 当前查询索引
priority_queue<int> qd;  // 大根堆，存储当前最小的k个元素
priority_queue<int, vector<int>, greater<int> > qx;  // 小根堆，存储剩余较大的元素int main()
{cin >> n >> m;  // 读入序列长度和查询次数// 读入序列afor (int i = 1; i <= n; i++){cin >> a[i];}// 读入查询位置bfor (int i = 1; i <= m; i++){cin >> b[i];}// 遍历序列afor (int i = 1; i <= n; i++){qd.push(a[i]);  // 将当前元素加入大根堆// 检查是否有查询位置等于当前索引iwhile (b[top] == i){// 调整大根堆大小，使其恰好包含top个元素while (qd.size() > top){// 将大根堆中最大的元素移到小根堆qx.push(qd.top());qd.pop();}// 此时大根堆的堆顶就是第top小的元素cout << qd.top() << endl;// 如果小根堆不为空，从其中取回一个元素保持平衡if (!qx.empty()){qd.push(qx.top());qx.pop();}top++;  // 处理下一个查询}}return 0;
}

【运行结果】

7 4
3 1 -4 2 8 -1000 2
1 2 6 6
3
3
1
2