nums라는 숫자 목록이 있다고 가정하고 주어진 목록의 모든 홀수 길이 하위 목록의 중앙값 합계를 찾아야 합니다.
따라서 입력이 nums =[2, 4, 6, 3]과 같으면 홀수 길이의 하위 목록이 − [2], [4], [6], [3]이므로 출력은 23이 됩니다. [2, 4, 6], [4, 6, 3]이므로 중앙값의 합은 2 + 4 + 6 + 3 + 4 + 4 =23입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ret :=0
-
initialize i :=0의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
que_max
라는 우선 순위 대기열을 정의합니다. -
que_min
이라는 다른 우선순위 큐를 정의하십시오. -
초기화 j :=i의 경우 j <숫자의 크기일 때 업데이트(j를 1만큼 증가), −
-
que_max
에 nums[j]를 삽입합니다. -
que_max의 크기>=2인 동안 −
-
que_max의 최상위 요소를 que_min에 삽입
-
que_max에서 최상위 요소 삭제
-
-
동안(que_min의 크기가 0이 아니고 que_max의 상위 요소> que_min의 상위 요소), 수행 -
-
a :=que_max의 최상위 요소, que_max에서 최상위 요소 삭제
-
b :=que_min의 최상위 요소, que_min에서 최상위 요소 삭제
-
que_max에 b 삽입
-
que_min에 삽입
-
-
i mod 2가 j mod 2와 같으면 -
-
ret :=ret + que_max의 최상위 요소
-
-
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int>& nums) {
int ret = 0;
for (int i = 0; i < nums.size(); i++) {
priority_queue<int> que_max;
priority_queue<int, vector<int>, greater<int>> que_min;
for (int j = i; j < nums.size(); j++) {
que_max.push(nums[j]);
while (que_max.size() - que_min.size() >= 2) {
que_min.push(que_max.top());
que_max.pop();
}
while (que_min.size() && que_max.top() > que_min.top()) {
int a = que_max.top();
que_max.pop();
int b = que_min.top();
que_min.pop();
que_max.push(b);
que_min.push(a);
}
if (i % 2 == j % 2) {
ret += que_max.top();
}
}
}
return ret;
}
int main(){
vector<int> v = {2, 4, 6, 3};
cout << solve(v);
} 입력
{2, 4, 6, 3} 출력
23