Pagini recente » Cod sursa (job #424811) | Cod sursa (job #819110) | Cod sursa (job #2375830) | Cod sursa (job #3243258) | Cod sursa (job #965657)
Cod sursa(job #965657)
//Heap constructed in O(n) with N elements, BFS search
#include<fstream>
#include<queue>
#include<algorithm>
using namespace std;
ifstream fin("sdo.in");
ofstream fout("sdo.out");
const int Nmax = 3000009;
int N; int K; int H[Nmax];
void Read(){
fin >> N >> K;
for(int i = 1; i <= N; ++i)
fin >> H[i];
}
void Percolate(int Pos){
int NextPos = Pos;
if( (Pos << 1) <= N && H[Pos << 1] < H[NextPos]) NextPos = (Pos << 1);
if( (Pos << 1) + 1 <= N && H[ (Pos << 1) + 1] < H[NextPos]) NextPos = (Pos << 1) + 1;
if(Pos != NextPos ){
swap(H[NextPos] , H[Pos]);
Percolate(NextPos);
}
}
void BuildHeap(){
for(int i = N; i >= 1; --i) Percolate(i);
}
class cmp{
public: bool operator()(const int &X, const int &Y){
return H[X] > H[Y];
}
};
void BFS(){
priority_queue< int, vector<int> , cmp> Q; Q.push(1);
for(int i = 1; i < K; ++i){
int t = Q.top();
Q.pop();
if(Q.size() == K) continue;//the lowest k numbers, useless to reatin more
if(t * 2 <= N) Q.push(t * 2);
if(t * 2 + 1 <= N) Q.push(t * 2 + 1);
}
fout << H[Q.top()];
//while(!Q.empty()) Q.pop();
}
int main(){
Read ();
BuildHeap ();
BFS();
return 0;
}