빈 시퀀스와 처리해야 하는 n개의 쿼리가 있다고 가정합니다. 쿼리는 배열 쿼리로 제공되며 {query, data} 형식입니다. 쿼리는 다음 세 가지 유형이 될 수 있습니다.
-
쿼리 =1:시퀀스의 끝에 제공된 데이터를 추가합니다.
-
쿼리 =2:시퀀스의 시작 부분에 요소를 인쇄합니다. 그런 다음 요소를 삭제합니다.
-
쿼리 =3:시퀀스를 오름차순으로 정렬합니다.
쿼리 유형 2와 3은 항상 데이터 =0입니다.
따라서 입력이 n =9와 같으면 쿼리 ={{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}, 그러면 출력은 5와 1이 됩니다.
각 쿼리 이후의 순서는 다음과 같습니다. -
- 1:{5}
- 2:{5, 4}
- 3:{5, 4, 3}
- 4:{5, 4, 3, 2}
- 5:{5, 4, 3, 2, 1}
- 6:{4, 3, 2, 1} , 5를 인쇄합니다.
- 7:{1, 2, 3, 4}
- 8:{2, 3, 4}, 1을 인쇄합니다.
- 9:{2, 3, 4}
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
priority_queue<int> priq
Define one queue q
for initialize i := 0, when i < n, update (increase i by 1), do:
operation := first value of queries[i]
if operation is same as 1, then:
x := second value of queries[i]
insert x into q
otherwise when operation is same as 2, then:
if priq is empty, then:
print first element of q
delete first element from q
else:
print -(top element of priq)
delete top element from priq
otherwise when operation is same as 3, then:
while (not q is empty), do:
insert (-first element of q) into priq and sort
delete element from q 예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
void solve(int n, vector<pair<int, int>> queries){
priority_queue<int> priq;
queue<int> q;
for(int i = 0; i < n; i++) {
int operation = queries[i].first;
if(operation == 1) {
int x;
x = queries[i].second;
q.push(x);
} else if(operation == 2) {
if(priq.empty()) {
cout << q.front() << endl;
q.pop();
} else {
cout << -priq.top() << endl;
priq.pop();
}
} else if(operation == 3) {
while(!q.empty()) {
priq.push(-q.front());
q.pop();
}
}
}
}
int main() {
int n = 9; vector<pair<int, int>> queries = {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}};
solve(n, queries);
return 0;
} 입력
9, {{1, 5}, {1, 4}, {1, 3}, {1, 2}, {1, 1}, {2, 0}, {3, 0}, {2, 0}, {3, 0}}
출력
5 1