[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)
Nhớ quê ra đứng đỉnh đèo, bỗng đâu thấy một chú mèo .. gâu gâu!
Dừng chân đứng lại trên cầu, bỗng đâu thấy một con trâu vàng vàng..
Subscribe to:
Post Comments (Atom)
Popular posts
-
(Written in English, since I've just got Grammarly installed and curious to see how it works). Since I came to college, many ...
-
MateQuiz is a site that allows you to create a quiz and challenge your friend's knowledge about you. This site's advantage is i...
-
Vậy là sau 4 năm thì tụi mình cũng chuẩn bị cút khỏi trường.
-
This is a summary of how difficult a fresh graduate could face when finding a job these days, in my own experience.
No comments:
Post a Comment