題目：最佳牛圍欄

題目鏈接：https://www.acwing.com/problem/content/104/

題意：農夫約翰的農場由 N 塊田地組成，每塊地里都有一定數量的牛，其數量不會少于 1 頭，也不會超過 2000 頭。

?? ? ?約翰希望用圍欄將一部分連續的田地圍起來，并使得圍起來的區域內每塊地包含的牛的數量的平均值達到最大。

?? ? ?圍起區域內至少需要包含 F 塊地，其中 F 會在輸入中給出。

?? ? ?在給定條件下，計算圍起區域內每塊地包含的牛的數量的平均值可能的最大值是多少？

思路：
?? ?找平均值/最小（大）值的最大（小）值，往二分答案方向想，二分答案的模板見代碼。我們在每一次假設答案的計算過程中，將數組都減去mid方便計算（也就是只要存在滿足條件同時大于0的字段就可以返回true了）
?? ?因為是找連續的一段，我們用前綴和優化計算，假設前綴和數組為pre，只要存在pre[j]-pre[i]>=0且j-i>=f就可以返回true了。

#include<bits/stdc++.h>using namespace std;using ll = long long;
const ll N = 100005;
const ll mod = 1e9 + 7;
const int maxn = 2005;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;
}int n, f;
int a[N];
double pre[N];bool check(double m) {for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + a[i] * 1.0 - m;}double minn = 0;for (int i = 0, j = f; j <= n; j++, i++) {minn = min(minn, pre[i]);if (pre[j] >= minn)return true;}return false;
}void solve() {cin >> n >> f;for (int i = 1; i <= n; i++) {cin >> a[i];}double l = 1, r = 2002;while (r-l>=1e-5) {double mid = (l + r) / 2;if (check(mid)) {l = mid;}elser = mid;}cout << (int)(r * 1000) << '\n';}signed main() {ios::sync_with_stdio(false);cin.tie(0);std::cout.tie(0);int t = 1; //cin >> t;while (t--)solve();return 0;
}