Cod sursa(job #375219)

Utilizator MciprianMMciprianM MciprianM Data 19 decembrie 2009 21:24:47
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<fstream>
using namespace std;
#define MAXN 3000009
unsigned int h[MAXN], hsize;
ofstream g("sdo.out");
void heapify(unsigned int x){
	unsigned int imin, aux;
	imin=x;
	do{
		x=imin;
		if(2*x<=hsize)
			if(h[2*x]<h[x])
				imin=2*x;
		if(2*x+1<=hsize)
			if(h[2*x+1]<h[imin])
				imin=2*x+1;
		aux=h[imin];
		h[imin]=h[x];
		h[x]=aux;
	}while(imin!=x && x<=hsize);
}
void make_heap(){
	int i;
	for(i=hsize/2;i>0;i--)
		heapify(i);
}
void pop(){
	//g<<h[1]<<'\n';
	h[1]=h[hsize--];
	heapify(1);
}
int main(){
	unsigned int n, k, i;
	ifstream f("sdo.in");
	f>>n>>k;
	for(i=1;i<=n;i++)
		f>>h[i];
	f.close();
	hsize=n;
	make_heap();
	while(--k)
		pop();
	
	g<<h[1]<<'\n';
	g.close();
	return 0;
}