最佳牛围栏
题意
农夫约翰的农场由 N 块田地组成，每块地里都有一定数量的牛，其数量不会少于 1 头，也不会超过 2000 头。
约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。
围起区域内至少需要包含 F 块地，其中 F 会在输入中给出。
在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。
思路
原题意为：求一个平均数最大的，长度不小于 F 的连续子段
二分答案，判断是否存在一个长度不小于 F 的子段，其平均值不小于二分的值
若将此区间元素都减去二分的值，问题即转变为：判断是否存在一个长度不小于 F 的子段，子段和非负
下面说明这一题为什么可以二分，假设最优值为 S ，二分的值为 mid，若mid <= S，说明可以找到一个长度不小于 F 的连续子段，平均值为 mid ，否则一定找不到。
对于二分，二分是二分性而不是单调性 只要满足可以找到一个值一半满足条件一半不满足条件即可 而不一定必须满足单调性
所以可以使用二分。
接下来讨论如何求一个子段，它的和最大，且长度大于等于 F
代码
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e5 + 10; int n, f; double a[N], sum[N], b[N]; void solve() { cin >> n >> f; for (int i = 1; i <= n; ++i)cin >> a[i]; double l = 0, r = 2100; // 二分答案 while (r - l > 1e-5) { double mid = (l + r) / 2; for (int i = 1; i <= n; ++i)b[i] = a[i] - mid; for (int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + b[i]; // 求最大子段和 double minn = INF, res = 0.0; for (int i = f; i <= n; ++i) { minn = min(minn, sum[i - f]); res = max(res, sum[i] - minn); } if (res > 0.0)l = mid; else r = mid; } cout << int(r * 1000) << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
