首页 > 代码库 > poj 1442 Black Box
poj 1442 Black Box
题目链接：http://poj.org/problem?id=1442
思路：
维护一个最小堆与最大堆，最大堆中存储最小的K个数，其余存储在最小堆中
代码：
#include<iostream>#include<queue>using namespace std;struct cmp1{ bool operator() ( const int a, const int b ) { return a > b; }};struct cmp2{ bool operator()( const int a, const int b ) { return a < b; }};priority_queue<int,vector<int>,cmp1>MaxHeap;priority_queue<int,vector<int>,cmp2>MinHeap;int a[30000];int main(){ int m, n, i, K; int Count = 0, Tmp; scanf( "%d%d", &m, &n ); for ( i = 0; i < m; i++ ) scanf( "%d", &a[i] ); for( i = 0; i < n; i++ ) { scanf( "%d", &K ); while ( Count < K ) { MaxHeap.push(a[Count]); if( !MinHeap.empty() && MaxHeap.top() < MinHeap.top() ) { Tmp = MaxHeap.top(); MaxHeap.pop(); MaxHeap.push( MinHeap.top() ); MinHeap.pop(); MinHeap.push(Tmp); } Count++; } printf( "%d\n", MaxHeap.top() ); MinHeap.push( MaxHeap.top() ); MaxHeap.pop(); }}
poj 1442 Black Box
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。