Solutions of Average

Select solution language

hovuviettruong Created at 15 likes

$\frac{(A_{l} + A_{l+1} +... + A_{r})}{(r - l + 1)} = k $ $=> \frac{(A_{l} + A_{l + 1} + .. + A_{r})}{(r - l + 1)} - k = 0 $ $=> \frac{(A_{l} + A_{l + 1} + .. + A_{r})}{r - l + 1} - \frac{k * (r - l + 1)}{r - l + 1} = 0 $ (Quy Đồng) $=> \frac{( A_{l} + A_{l + 1} + ... + A_{r}) - k * (r - l + 1) }{r - l + 1} = 0 $ $=> \frac{(A_{l} - k + A_{l + 1} - k + ... + A_{r} - k)}{r - l + 1} = 0 $ $=> A_{l} - k + A_{l + 1} - k + ... + A_{r} - k = 0 $ (Nhân 2 vế cho $r - l + 1$) Đến Đây chỉ cần dùng $Prefixsum$, đếm dãy có tổng = 0 $Pre_{i} = Pre_{i - 1} + A_{i} - k $

nhanzzzz Created at 9 likes

***phân tích*** + gọi x là độ dài của đoạn con + $(A_1 + A_2 + A_3 + A_4 + ... + A_x) / x = k$ + $(A_1 + A_2 + A_3 + A_4 + ... + A_x) = k*x$ + $(A_1 - k + A_2 - k + A_3 - k + A_4 - k + ... + A_x - k) = 0$ ***thực hiện*** + trừ k vào tất cả các phần tử + đếm các đoạn con có tổng bằng 0 ***code mẫu*** ``` #include <bits/stdc++.h> #define int long long using namespace std; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int n,k; cin >> n >> k; vector<int> arr(n); for(int i=0;i<n;i++){ cin >> arr[i]; arr[i] -= k; } // int cs = 0, t = 0; unordered_map<int,int> d; d[0] = 1; for(int i: arr){ cs += i; if(d.find(cs) != d.end()){ t += d[cs]; } d[cs]++; } // cout << t; return 0; } ```