#include <sstream>
#include <vector>
#include <queue>
#include <stdlib.h>
#include <iomanip>
using namespace std;
void GetMedian(int arr[], int len)
{
priority_queue <int, vector <int>, greater <int>> minheap;
priority_queue <int, vector <int>, less <int>> maxheap;
int i, x;
for (i=0; i<len; i++)
{
x = arr[i];
if (!maxheap.empty() && x > maxheap.top()) {
minheap.emplace(x);
} else {
maxheap.emplace(x);
}
if (minheap.size() > maxheap.size() + 1) {
maxheap.emplace(minheap.top());
minheap.pop();
} else if (maxheap.size() > minheap.size() + 1) {
minheap.emplace(maxheap.top());
maxheap.pop();
}
cout << fixed;
cout << setprecision(1);
if (minheap.size() == maxheap.size()) {
cout << (double) (0.5 * (minheap.top() + maxheap.top())) << endl;
} else {
cout << (double) ((minheap.size() > maxheap.size() ? minheap.top() : maxheap.top())) << endl;
}
}
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int N, i;
cin >> N;
int A[N];
for (i = 0; i < N; i++)
{
cin >> A[i];
}
GetMedian(A, N);
return 0;
}
No comments:
Post a Comment