PAIRS1 - Count the pairs

[Tutorial] SPOJ

Đề bài: Cho N số nguyên (0 < N <= 10^5), tìm số lượng các cặp số nguyên chênh lệch nhau một lượng K. Tất cả số liệu đều nằm trong phạm vi 32bits integers.

(Giải thích: Giả sử ta có N số nguyên lần lượt là a[1], a[2], ..., a[N]. Gọi i, j là chỉ số của 2 số nguyên trong dãy a, i khác j. Nếu abs(a[i] - a[j]) = K thì a[i] và a[j] là một cặp số thỏa yêu cầu đề bài).

Input: 2 dòng: dòng đầu tiên là hai số nguyên N và K, dòng tiếp theo là N số nguyên cách nhau bởi một khoảng trắng, các số trong dãy là phân biệt (không có 2 số trùng nhau trong dãy).

Output: một số nguyên là tổng số cặp số chênh lệch một lượng K thỏa yêu cầu đề bài.

Ví dụ:
Input:
5 2
1 5 3 4 2
Output:
3
(Các cặp thỏa mãn yêu cầu: [0, 2], [1, 4], [3, 4]).

Input:
10 1  
363374326 364147530 61825163 1073065718 1281246024 1399469912 428047635 491595254 879792181 1069262793 
Output:
0
(Không có cặp nào thỏa yêu cầu của đề bài)

Solution: sorting + binary search.
Sử dụng ví dụ 1: dãy số a sau khi sắp xếp lại:
1 5 3 4 2 thành 1 2 3 4 5.
Với mỗi phần tử a[i] trong dãy a, ta tìm kiếm phần tử a[x] sao cho a[i] + k = a[x]. Nếu a[x] tồn tại thì a[i] và a[x] là một cặp thỏa yêu cầu đề bài.

Code mẫu (C++, sử dụng thư viện algorithm có sẵn hàm sort và binary_search)