backjoon 2696 문제 풀이

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);

#if 0

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

mi_q.push(40);

mi_q.push(17);

mi_q.push(30);

mi_q.push(20);

mi_q.push(10);

cout << "top : " << mi_q.top() << endl;  

#endif 

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>> minq; //내림 차순  // 5 4 3 2 1  

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

cin >> arr[0];

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

maxq.push(arr[0]);

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

cin >> arr[i];

maxq.push(arr[i]);

cin >> arr[++i];

minq.push(arr[i]);

if (maxq.top() > minq.top()){

//swap

maxq.push(minq.top()); 

minq.pop();

minq.push(maxq.top()); 

maxq.pop();

}

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

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

}

cout << endl;

delete [] arr;

}

return 0;

}