백준 중앙값 구하기 문제

백준 ..문제 

https://www.acmicpc.net/problem/2696

핵심 key 는 priority queue 두개를 통해 각각 swap 을 하던지 해서 정렬 시켜 줘야함 

#include <stdio.h>

#include <iostream>    //cout

#include <vector>

#include <cmath>

#include <string>

#include <utility>

#include <map>

#include <set>

#include <queue>

#include <functional>

#include<algorithm>

using namespace std;

#pragma warning(disable : 4996)

int main(void){

    int N, T;

    int tmp;

    freopen("sample_input.txt", "r", stdin);

    setbuf(stdout, NULL);

    

    cin >> T;

    int n, num;

    

    for (int i = 1; i <= T;i++ ){ //case number 

        cin >> n;

        cout << (n + 1) / 2 << endl;

        int *arr = new int[n + 1];

        priority_queue<int, vector <int>, greater<int>> up; //내림 차순  // 5 4 3 2 1  

        priority_queue<int, vector <int>, less<int>> down;    //오름 차순  // 1 2 3 4 5

        cin >> arr[0];

        cout << arr[0]<< " ";

        down.push(arr[0]);

        for (int i = 1; i < n; i++)  {

            cin >> arr[i];

            down.push(arr[i]);

            cin >> arr[++i];

            up.push(arr[i]);

            if (down.top() > up.top() ){

                int u = down.top();

                up.push(u);

                down.pop();

                

                int d = up.top();

                down.push(d);

                up.pop();

            }

            if (i % 20 == 0) cout << endl;

            cout << down.top() << " ";            

        }    

        cout << endl;

        delete [] arr;

    }

    return 0;

}