두 배의 역전
플래티넘 V의견: 0
나라야나 기록 보관소에는 길이 \(N\)의 정수 수열 \(a_1, a_2, \dots, a_N\) 이 보관되어 있다. 보관소 사서는 이 수열에서 '심각한 역전(significant inversion)' 의 개수를 세려고 한다.
순서쌍 \((i, j)\) 가 다음 두 조건을 모두 만족하면 심각한 역전이라고 부른다.
- \(i < j\)
- \(a_i > 2 \cdot a_j\)
즉 앞쪽 원소가 뒤쪽 원소의 두 배보다 큰 경우를 센다. \(N\)이 매우 크므로 모든 쌍을 직접 비교하는 \(O(N^2)\) 방법으로는 제한 시간 안에 풀 수 없다. 분할 정복(병합 정렬)을 이용하면 \(O(N \log N)\) 에 셀 수 있다.
\(1 \le N \le 200{,}000\)
\(-10^9 \le a_i \le 10^9\)
첫째 줄에 수열의 길이 \(N\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 주어진다.
심각한 역전의 개수를 한 줄에 출력한다.
6
5 -1 2 0 -3 8
8심각한 역전 쌍은 \((a_1,a_3)=(5,2)\) 에서 \(5>4\), \((a_1,a_4)=(5,0)\) 에서 \(5>0\), \((a_1,a_5)=(5,-3)\) 에서 \(5>-6\), \((a_3,a_5)=(2,-3)\) 에서 \(2>-6\), \((a_6\) 관련 없음\()\) 등이다. 직접 세어 보면 총 5개이다.
4
1 2 3 4
0수열이 순증가하므로 \(a_i > 2a_j\) 인 쌍이 하나도 없다. 따라서 답은 0이다.
riseoj 작성
출처 Original
평가 및 의견
두 배의 역전
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
두 배의 역전