### Tóm tắt bài toán
Bài toán yêu cầu ta tìm dãy con có độ dài ít nhất là $k$ có trung bình cộng lớn nhất.
Ta có thể viết lại thành việc tìm hai chỉ số $i, j$ sao cho:$$
\frac{\sum_{t = i}^{j} A_t}{j - i + 1}$$là giá trị lớn nhất có thể.
---
### Hướng giải
Ta cần tìm giá trị $x$ lớn nhất sao cho tồn tại hai chỉ số $i, j$ thỏa mãn:$$
\frac{\sum_{t = i}^{j} A_t}{j - i + 1} \geq x
$$Ta có thể sử dụng chặt nhị phân để tìm giá trị $x$, với đoạn chặt từ $\min(A)$ đến $\max(A)$.
> Lưu ý: Khi cài đặt trong C++, nên so sánh với một giá trị epsilon nhỏ (ví dụ $10^{-7}$) để tránh lỗi làm tròn số thực (`floating point error`).
#### Xây dựng hàm kiểm tra $f(x)$
Để xác định xem một giá trị $x$ có khả thi hay không, ta cần kiểm tra xem có tồn tại một đoạn con có trung bình cộng $\geq x$.
Nhận xét:$$
\frac{\sum_{t = i}^{j} A_t}{j - i + 1} \geq x
\Leftrightarrow \sum_{t = i}^{j} A_t \geq (j - i + 1) \times x
\Leftrightarrow \sum_{t = i}^{j} (A_t - x) \geq 0 $$Từ đó, ta tạo một mảng prefix sum mới: $$pf[i] = \sum_{t = 1}^{i} (A_t - x)$$ Để kiểm tra xem có đoạn con độ dài $\geq k$ thỏa mãn điều kiện trên, ta chỉ cần xét:
- Với mỗi vị trí $i \geq k$, tìm giá trị nhỏ nhất của $pf[i - k]$ trước đó.
- Nếu tồn tại $pf[i] - min(pf[i - k]) \geq 0$, thì có ít nhất một đoạn con có trung bình $\geq x$.
---
### Độ phức tạp
- Mỗi lần kiểm tra $f(x)$ có độ phức tạp $O(n)$.
- Số lần chặt nhị phân khoảng $O(log(\text{precision}))$, thường là ~60 lần cho độ chính xác $10^{-7}$.
$\Rightarrow$ Tổng thời gian: $O(n log(\text{precision}))$, rất hiệu quả cho $n ≤ 10^5$.
---
### Code tham khảo
```cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<float> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
float l = minall(a), r = maxall(a), ans = 0.0, eps = 1e-7;
while (r - l >= eps)
{
float m = (l + r) / 2.0;
auto f = [&](float m)
{
vector<float> pf(n + 1, 0.0);
for (int i = 0; i < n; i++)
pf[i + 1] = pf[i] + a[i] - m;
float mn = 0.0;
for (int i = k; i <= n; i++)
{
mn = min(mn, pf[i - k]);
if (pf[i] - mn >= 0)
return true;
}
return false;
};
if (f(m))
ans = m, l = m;
else
r = m;
}
cout << fixed << setprecision(6) << ans;
}
```
Defylogicguy
Created at
1 likes