문제 링크 : https://www.acmicpc.net/problem/2696
이 문제는 백준 1655 가운데를 말해요 와 완전히 동일한 문제 입니다.
차이가 있다면, 벡터를 하나 더 구한 후 홀수번째를 만났을 때 벡터에 현재의 중간값을 넣어준다는 것 입니다.
소스코드 :
이 문제는 백준 1655 가운데를 말해요 와 완전히 동일한 문제 입니다.
차이가 있다면, 벡터를 하나 더 구한 후 홀수번째를 만났을 때 벡터에 현재의 중간값을 넣어준다는 것 입니다.
소스코드 :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <queue>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
for (int t = 0; t < T; t++) {
int n;
cin >> n;
vector<int> v;
priority_queue<int> maxHeap;
priority_queue<int, vector<int>, greater<int> > minHeap;
for (int i = 1; i <= n; i++) {
int num;
cin >> num;
if (maxHeap.size() == minHeap.size()) {
maxHeap.push(num);
}
else {
minHeap.push(num);
}
if (!minHeap.empty() && !maxHeap.empty() && minHeap.top() < maxHeap.top()) {
int a = maxHeap.top(), b = minHeap.top();
maxHeap.pop();
minHeap.pop();
maxHeap.push(b);
minHeap.push(a);
}
//cout << maxHeap.top() << '\n';
if (i % 2 != 0) {
v.push_back(maxHeap.top());
}
}
std::cout << v.size() << '\n';
for (int i = 0; i < v.size(); i++) {
std::cout << v[i] << ' ';
}
std::cout << '\n';
}
}
| cs |
댓글
댓글 쓰기