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)
- 3
Ap = Ai + Aj + Ak => 3Ap - Ak = Ai + Aj

Thuật O(n^2log2(n^2))


Code: copy code

Posted on June 11, 2021 10:45:30 PM


1
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.