poj 2388(スタックソート)
#include <iostream>
using namespace std;
#define swap(a, b) {int t = a; a = b; b = t;}
int A[10001], size;
int parent(int i) {
return i/2;
}
int left(int i) {
return i*2;
}
int right(int i) {
return i*2+1;
}
void max_heapify(int i)
{
int l, r, largest;
l = left(i);
r = right(i);
if(l <= size && A[l] > A[i]) {
largest = l;
}
else {
largest = i;
}
if(r <= size && A[r] > A[largest]) {
largest = r;
}
if(i != largest) {
swap(A[i], A[largest]);
max_heapify(largest);
}
}
void build_max_heap()
{
for(int i = size/2; i >= 1; i--) {
max_heapify(i);
}
}
void heap_sort()
{
build_max_heap();
for(int i = size; i >= 2; i--) {
swap(A[1], A[i]);
size -= 1;
max_heapify(1);
}
}
int main()
{
int n;
while(scanf("%d", &n) != EOF) {
for(int i = 1; i <= n; i++)
scanf("%d", &A[i]);
size = n;
heap_sort();
printf("%d
", A[n/2+1]);
}
return 0;
}
2388
Accepted
208K
16MS