每日一题: Best Cow Fences(二分)

题意

给定一个正整数数列A，求一个平均数最大的、长度不小于L的子段。

solution

考虑check问题，正着枚举起点，我们需要知道每个起点所能枚举的最大值。当一个数大于当前二分的平均数时，它一定是对答案有贡献的，因此倒过来预处理每个起点能枚举到的最大值即可。时间复杂度 $O(nlogn)$。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;

ll n, k;
double a[N], sum[N], pre[N];

bool check(double avg) {
  pre[n + 1] = 0;
  for (ll i = n; i >= 1; i--) pre[i] = max(a[i] - avg, pre[i + 1] + a[i] - avg);
  for (ll i = 0; i <= n - k; i++) {
    if (sum[i + k] - sum[i] >= k * avg) return true;
    if (sum[i + k] - sum[i] + pre[i + k + 1] >= k * avg) return true;
  }
  return false;
}

int main() {
  while (~scanf("%lld%lld", &n, &k)) {
    double l = 1e18 + 7, r = 0, mid;
    for (ll i = 1; i <= n; i++) {
      scanf("%lf", &a[i]);
      l = min(l, a[i]);
      r = max(r, a[i]);
      sum[i] = sum[i - 1] + a[i];
    }
    while (r - l > 0.0001) {
      mid = (l + r) / 2.0;
      if (check(mid))
        l = mid;
      else
        r = mid;
    }
    printf("%lld\n", (ll)(l + 0.5));
  }
  return 0;
}