POJ - 1442 Black Box

本文主要是介绍POJ - 1442 Black Box，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.题面

传送门

2.解题思路

解题思路1-双优先队列解法

这是我第二次见到有人使用treap求解第K大值了，看来有必要学习一下treap了。这道题我是使用两个堆做的，解这道题目我们需要维护两个堆，一个大顶堆，一个小顶堆，只需要这两个堆满足以下三个条件：

1.大顶堆和小顶堆的元素并为全集

2.大顶堆和小顶堆中没有重叠元素（这个重叠不太好说，我们先假设所有的元素都是不一样的，这样比较容易理解）

3.大顶堆的堆顶要小于小顶堆的堆顶

4.大顶堆的size是k

在这样的情况下，我们可以说大顶堆的堆顶是整个集合中的第K个元素。

证明应该不需要多说，可以理解小顶堆中所有的元素都比大顶堆的堆顶要大，大顶堆中所有的元素除了堆顶，都比堆顶元素要小，自然大顶堆堆顶就是第K大的元素了。

为了实现这样的条件来查找第K大的值，我们只需要两步

第一步：调整大顶堆元素为K，当大顶堆元素不足K时，从小顶堆中弹出元素压入大顶堆中；当大顶堆中元素大于K时，从大顶堆中弹出元素放入小顶堆中

第二步：调整大顶堆堆顶小于小顶堆堆顶。当大顶堆堆顶大于小顶堆堆顶时，分别弹出两个堆顶元素，并压入另一个堆中。

然后就OK啦

事实上这样的调整复杂度还是O（nlogn），但常数要小很多，最终还过了。然后在使用STL的时候要时时刻刻记得查看stack，queue，priority_queue是不是空的，经常为因为忘记这个出错。

解题思路2-Treap求第K小值

表示Treap是我见过的平衡树中最容易实现的了，插入只有两种旋转方式，删除时如果采用将孩子节点中较小的孩子旋转上来的话，也很容易实现。如果输入数据有多组也许要清理一下之前分配的内存，因为这道题只有一组数据，所以不清理也是可以的，而且更重要的原因是，清理消耗时间比较多，而竞赛中对于时间的限制要远远比对于空间的限制严格。我尝试了一下清理数据，发现慢了几十毫秒，应该是是可以承受的。

最终，查找第K小值的时候，你只需要根据左子树中元素的个数，以及自身元素重复的次数，就可以确定你应当到右子树中去搜索还是去左子树中搜索，还是你已经找到了答案。个人感觉这个函数能比较简单地写成while循环，有时间我去改改。

PS：我写的代码是支持重复元素的插入删除与查找K值的，但是这道题并没有说是否存在重复元素，所以虽然AC了，还不能确定这个功能是完全正确的。

3.解题代码

解题代码1-双优先队列

/*****************************************************************> File Name: tmp.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年02月24日 星期三 18时44分40秒****************************************************************/
# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;const int debug = 1;
const int size  = 100000 + 10; 
typedef long long ll;ll add[size],get[size];
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);int i,j,k;int n,m;priority_queue<ll,vector<ll>,greater<ll> > minheap;priority_queue<ll,vector<ll>,less<ll> > maxheap;ll tmp;while (cin >> m >> n){while (!minheap.empty())	minheap.pop();while (!minheap.empty())	maxheap.pop();for (i=1;i<=m;i++){cin >> add[i];}for (i=1;i<=n;i++){cin >> get[i];}k = 1;for (i=1;i<=n;i++){for (;k<=get[i];k++){minheap.push(add[k]);}int s = k-1;while (maxheap.size()>i){minheap.push(maxheap.top());maxheap.pop();}while (maxheap.size()<i){maxheap.push(minheap.top());minheap.pop();}if (!minheap.empty()&&!maxheap.empty())while (minheap.top()<maxheap.top()){ll t1 = maxheap.top();maxheap.pop();ll t2 = minheap.top();minheap.pop();minheap.push(t1);maxheap.push(t2);}cout << maxheap.top() << '\n';}}return 0;
}

解题代码2-Treap查找第K大值

/*****************************************************************> File Name: tmp.cpp> Author: Uncle_Sugar> Mail: uncle_sugar@qq.com> Created Time: 2016年02月27日 星期六 17时20分14秒
*****************************************************************/
# include <cstdio>
# include <cstring>
# include <cmath>
# include <cstdlib>
# include <climits>
# include <iostream>
# include <iomanip>
# include <set>
# include <map>
# include <vector>
# include <stack>
# include <queue>
# include <algorithm>
using namespace std;const int debug = 0;
const int size  = 1000000 + 10;
typedef long long ll;# ifndef ONLINE_JUDGE
struct DesktopIO{DesktopIO(){freopen("//home//unclesugar//in.txt","r",stdin);freopen("//home//unclesugar//out.txt","w",stdout);}
}DIO;
# endifstruct Treap_Node{int value;int fix,cnt,size;Treap_Node *left,*right;Treap_Node():cnt(0),size(0),left(NULL),right(NULL){}Treap_Node(int _value):value(_value),cnt(0),size(0),left(NULL),right(NULL){}
}*root = NULL;
inline void Treap_SetSize(Treap_Node *&P){if (P){P->size = P->cnt;if (P->left)	P->size += P->left->size;if (P->right)	P->size += P->right->size;}
}
inline int lsize(Treap_Node *&P){return P->left?P->left->size:0;
}
inline int rsize(Treap_Node *&P){return P->right?P->right->size:0;
}
void Treap_Left_Rotate(Treap_Node *&a){Treap_Node *b = a->right;a->right = b->left;b->left = a;a = b;Treap_SetSize(a->left);Treap_SetSize(a->right);Treap_SetSize(a);
}
void Treap_Right_Rotate(Treap_Node *&a){Treap_Node *b = a->left;a->left = b->right;b->right = a;a = b;Treap_SetSize(a->left);Treap_SetSize(a->right);Treap_SetSize(a);
}
void Treap_Insert(Treap_Node *&P,int value){if (!P){P = new Treap_Node;P->value = value;P->fix = rand();}if (value < P->value){Treap_Insert(P->left,value);if (P->left->fix < P->fix)Treap_Right_Rotate(P);}else if (P->value < value){Treap_Insert(P->right,value);if (P->right->fix < P->fix)Treap_Left_Rotate(P);}else {P->cnt++;}Treap_SetSize(P);
}
Treap_Node* Treap_Findkth(Treap_Node *&P,int k){if (k <= lsize(P))return Treap_Findkth(P->left,k);else if (k > lsize(P)+P->cnt)return Treap_Findkth(P->right,k-(lsize(P)+P->cnt));elsereturn P;
}
void Treap_Clear(Treap_Node *&root){if (root->left)Treap_Clear(root->left);if (root->right)Treap_Clear(root->right);delete root;root = NULL;
}int data[size];
int query[size];
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);int i,j,k,tmp;int n,m;while (cin >> n >> m){for (i=0;i<n;i++)cin >> data[i];for (i=0;i<m;i++)cin >> query[i];for (k=i=0;i<m;i++){while (k<query[i]){Treap_Insert(root,data[k]);k++;}Treap_Node *T = Treap_Findkth(root,i+1);cout << T->value << '\n';}Treap_Clear(root);}return 0;
}