차이가 작은 쌍 세기
실버 III의견: 0
\(N\)개의 정수가 주어진다. 두 원소를 고르는 순서 없는 쌍 \(\{i, j\}\)(\(i \ne j\)) 중에서, 두 값의 차이의 절댓값이 \(D\) 이하인 쌍의 개수를 출력하여라.
쌍의 수가 매우 많을 수 있으므로 모든 쌍을 일일이 확인하는 방법으로는 시간 안에 답할 수 없다.
\(1 \le N \le 100\,000\), \(0 \le D \le 10^9\), 각 원소는 \(1\) 이상 \(10^9\) 이하이다.
첫째 줄에 원소의 개수 \(N\)과 정수 \(D\)가 주어진다. 둘째 줄에 \(N\)개의 정수가 공백으로 구분되어 주어진다.
값의 차이가 \(D\) 이하인 순서 없는 쌍의 개수를 출력한다.
4 2
1 3 5 4
4차이가 \(2\) 이하인 쌍은 \(\{1,3\}, \{3,5\}, \{3,4\}, \{5,4\}\)로 \(4\)개이다.
3 0
5 5 5
3세 원소가 모두 같아 차이가 \(0\)인 쌍이 \(3\)개이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
차이가 작은 쌍 세기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
차이가 작은 쌍 세기