域名与网站建设,西安谷歌推广,免费房屋装修设计,网站排名怎么做的题目描述
Black Box 是一种原始的数据库。它可以储存一个整数数组#xff0c;还有一个特别的变量 i。最开始的时候 Black Box 是空的#xff0e;而 i0。这个 Black Box 要处理一串命令。
命令只有两种#xff1a; ADD(x)#xff1a;把 x 元素放进 Black Box; GET#x…题目描述
Black Box 是一种原始的数据库。它可以储存一个整数数组还有一个特别的变量 i。最开始的时候 Black Box 是空的而 i0。这个 Black Box 要处理一串命令。
命令只有两种 ADD(x)把 x 元素放进 Black Box; GETi 加 1然后输出 Black Box 中第 i 小的数。
记住第 i 小的数就是 Black Box 里的数的按从小到大的顺序排序后的第 i 个元素。
我们来演示一下一个有11个命令的命令串。如下表所示
序号操作i数据库输出1ADD(3)03/2GET1333ADD(1)11,3/4GET21,335ADD(-4)2−4,1,3/6ADD(2)2−4,1,2,3/7ADD(8)2−4,1,2,3,8/8ADD(-1000)2−1000,−4,1,2,3,8/9GET3−1000,−4,1,2,3,8110GET4−1000,−4,1,2,3,8211ADD(2)4−1000,−4,1,2,2,3,8/
现在要求找出对于给定的命令串的最好的处理方法。ADD 命令共有 m 个GET 命令共有 n 个。现在用两个整数数组来表示命令串 a1,a2,⋯,am一串将要被放进 Black Box 的元素。例如上面的例子中 a[3,1,−4,2,8,−1000,2]。 u1,u2,⋯,un表示第 ui 个元素被放进了 Black Box 里后就出现一个 GET 命令。例如上面的例子中 u[1,2,6,6] 。输入数据不用判错。
输入格式
第一行两个整数 m 和 n表示元素的个数和 GET 命令的个数。
第二行共 m 个整数从左至右第 i 个整数为 ai用空格隔开。
第三行共 n 个整数从左至右第 i 个整数为 ui用空格隔开。
输出格式
输出 Black Box 根据命令串所得出的输出串一个数字一行。
输入输出样例
输入 #1复制
7 4
3 1 -4 2 8 -1000 2
1 2 6 6输出 #1复制
3
3
1
2说明/提示
数据规模与约定
对于 30% 的数据1≤n,m≤104。对于 50% 的数据1≤n,m≤105。对于 100% 的数据1≤n,m≤2×105,∣ai∣≤2×109保证 u 序列单调不降。
代码实现
#include iostream #include vector #include queue #include algorithm
using namespace std;
int main() { int m, n; cin m n; vectorint a(m); for (int i 0; i m; i) { cin a[i]; } vectorint u(n); for (int i 0; i n; i) { cin u[i]; } priority_queueint maxHeap; priority_queueint, vectorint, greaterint minHeap; int ptr 0; // 当前处理到a的位置 int getCount 0; // 当前GET命令的数量 for (int i 0; i n; i) { int target u[i]; // 处理ADD操作直到ptr达到target while (ptr target) { int num a[ptr]; maxHeap.push(num); // 调整两个堆的平衡 if (maxHeap.size() getCount 1) { minHeap.push(maxHeap.top()); maxHeap.pop(); } } // 处理GET操作 getCount; cout maxHeap.top() endl; // 调整两个堆的平衡 if (!minHeap.empty()) { maxHeap.push(minHeap.top()); minHeap.pop(); } } return 0; }
