C++Solution VDSEQ04 - Giá trị trung bình
Được viết bởi: Hust IT1
Cho một dãy số nguyên A1, A2, ..., An.(2 < n <= 10^3; |Ai| <= 108). Một số Ap (1<=p<=n) được gọi là giá trị trung bình nếu tồn tại 3 chỉ số i, j, k (1<=i,j,k<=n) đôi một khác nhau sao cho:
3Ap = Ai + Aj + Ak
Bạn hãy lập trình đếm số lượng các giá trị trung bình của dãy số trên
Dữ liệu vào:
- Dòng 1 là số nguyên dương N
- Các dòng sau là dãy số A
Dữ liệu ra:
- Số lượng giá trị trung bình đếm được.
Ví dụ
input:
5
1
2
3
4
5
output:
3
Có 2 mấu chốt để AC bài này:
- Dùng chặt nhị phân (không dùng cấu trúc heap vì chậm hơn mảng + sort)
- 3Ap = Ai + Aj + Ak => 3Ap - Ak = Ai + Aj
Thuật O(n^2log2(n^2))
Code: copy code
