被精度气晕

题意:
给定一个长度为$n$的非负整数($ 1 \le A_i \le 2000 $)序列A，求一个平均数最大的，长度不小于 $f$ 的子段。输出表示平均值的最大值乘以 1000再向下取整 之后得到的结果

法1: 二分答案

既然要求最大的平均数，显然当平均数过大时就不存在了

所以要找到一个[l, r], 满足
$$\frac{\sum_{i=l}^ra_i}{r-l+1}\geq mid$$
转换得：
$$\sum_{i=l}^r(a_i-mid)\geq0$$

那么将序列中每个数减去mid，然后相当于求一个长度>=f的最大子段和，判断一下是否>=0即可。

实现二分check的时候，可以用前缀和优化
pre[i] = pre[i - 1] + a[i] - mid

时间复杂度： $O(N\log W)$

最后二分完只能输出r不能输出l

以样例为例，l最后结果为6499.99999, r最后结果为6500.000001 因为答案让向下取整，所以用r来输出

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const double eps = 1e-8;
const int N = 1e5 + 10;
int n, f, a[N];
double pre[N];
bool check(double mid) 
{
  for (int i = 1; i <= n; i++)
    pre[i] = pre[i - 1] + a[i] - mid;
  double minn = 2000; // minn存储pre[0, i - f]的最小值
  for (int i = f; i <= n; i++)
  {
    // 求以i作为右边界，长度不小于f的子段的最大值
    // 左边界最大为i - f + 1 能减的pre数组范围为[0, i - f] 更新一下这个范围中的最小值
    minn = min(minn, pre[i - f]);
    if (pre[i] - minn >= 0)
      return true;
  }
  return false;
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cin >> n >> f;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  double l = 0, r = 2000;
  while (r - l > eps)
  {
    double mid = (l + r) / 2;
    if (check(mid))
      l = mid;
    else
      r = mid;
  }
  cout << (int)(r * 1000);


  return 0;
}