题目
#10012 「一本通 1.2 例 2」Best Cow Fences
解析
有序列\(\{a_i\}\)，设\([l,r]\)上的平均值为\(\bar{x}\)，有\(\sum_{i=l}^r(a_i-\bar{x})=0\) 这样我们就可以通过二分平均值， 先同减二分到的平均值，若存在一段区间的和大于等于0，说明这段区间的平均值大于等于二分值，上调边界，否则下调边界
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;
int n, m;
double a[N], sum[N];
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
double l = -1000000.0, r = 1000000.0;
while (r - l > EPS) {
double mid = (l + r) / 2;
for (int i = 1; i <= n; ++i) sum[i] = a[i] - mid + sum[i - 1];
double ans = -INF, mn = INF;
for (int i = m; i <= n; ++i)
mn = min(mn, sum[i - m]), ans = max(ans, sum[i] - mn);
if (ans >= 0) l = mid;
else r = mid;
}
cout << int(r * 1000);
}
转载于:https://www.cnblogs.com/lykkk/p/11230662.html
