격차 큰 역전
플래티넘 V의견: 0
길이 \(N\)의 정수 수열 \(a_1, \dots, a_N\) 과 정수 \(D\)가 주어진다. 다음 조건을 모두 만족하는 순서쌍 \((i, j)\) 의 개수를 구하여라.
- \(i < j\)
- \(a_i - a_j \ge D\)
즉 앞 원소가 뒤 원소보다 \(D\) 이상 큰 경우(격차가 큰 역전)를 센다. \(N\)이 크므로 \(O(N^2)\) 비교로는 풀 수 없다. 병합 정렬 과정에서 두 정렬된 절반을 합칠 때 투 포인터로 조건을 만족하는 쌍의 수를 누적하는 분할 정복으로 \(O(N \log N)\) 에 해결할 수 있다.
\(1 \le N \le 200{,}000\)
\(-10^9 \le a_i \le 10^9\)
\(0 \le D \le 2 \times 10^9\)
첫째 줄에 \(N\)과 \(D\)가 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
조건을 만족하는 순서쌍의 개수를 출력한다.
5 3
10 4 7 1 6
6\(D=3\). 조건 \(a_i-a_j\ge3\) 을 만족하는 쌍은 \((10,4),(10,7),(10,1),(10,6),(7,1)\) 으로 총 5개이다.
4 0
2 2 2 2
6\(D=0\) 이므로 \(a_i-a_j\ge0\), 즉 \(a_i\ge a_j\) 인 모든 쌍을 센다. 모든 값이 같으므로 \(i
riseoj 작성
출처 Original
평가 및 의견
격차 큰 역전
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
격차 큰 역전