Farmer John's farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows <= 2000.
FJ wants to build a fence around a contiguous group of these fields in order to maximize the average number of cows per field within that block. The block must contain at least F (1 <= F <= N) fields, where F given as input.
Calculate the fence placement that maximizes the average, given the constraint.
Input
* Line 1: Two space-separated integers, N and F.
* Lines 2..N+1: Each line contains a single integer, the number of cows in a field. Line 2 gives the number of cows in field 1,line 3 gives the number in field 2, and so on.
Output
* Line 1: A single integer that is 1000 times the maximal average.Do not perform rounding, just print the integer that is 1000*ncows/nfields.
Sample Input
10 6 6 4 2 10 3 8 5 9 4 1
Sample Output
6500
中文概要：
要求去划分n个点，要求使得在一段长度不小于L的子区间中每个点得到的平均值最大，并输出这个最大的平均值。
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include<algorithm>
#include<iomanip>
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
#define mod 998244353
const int MAXN = 1e9 + 7;
const double PI = 3.14159265358979;
using namespace std;
const int N = 1e5 + 5;
/*int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
ll _power(int a, int b)//计算a^b;
{
int ans=1, res=a;
while(b){
if(b&1) ans=ans*res%mod;
res=res*res%mod;
b>>=1;
}
return ans%mod;
*/
double a[N], b[N], s[N];
double l, r,mid;
int n, f;
int main() {
scanf("%d%d", &n, &f);
for (int i = 1; i <= n; i++) {
scanf("%lf", &a[i]);
}
l = -1e6; r = 1e6;
s[0] = 0;
while (r-l>1e-5) {
mid = (l + r) / 2;
for (int i = 1; i <= n; i++) {
b[i] = a[i] - mid;
}
for (int i = 1; i <= n; i++) {//前缀和
s[i] = s[i - 1] + b[i];
}
double maxn, minn;
maxn = -1e10; minn = 1e10;
for (int i = f; i <= n; i++) {
minn = min(minn, s[i - f]);
maxn = max(maxn, s[i] - minn);
}
if (maxn >= 0) l = mid;
else r = mid;
}
printf("%d\n", (int)(r * 1000));
return 0;
}
思路：
二分答案+判定：
1、二分平均值 average
2、将所有的点减去 average
3、对区间求前缀和。
4、枚举每个长度为 L 的子区间，减去当前最小值，这时长度至少为 L（并且可能大于，这是满足要求的）。设：这次扫描得到的最大的 和 为 ans
5、
(1)、如果 这次找到的 ans 是小于0的，那么意味着，当前的 average 太大了，以至于没有任何一个子区间的平均值是能够达到当前的 average ，即：不存在满足当前 average 的情况。
(2)、否则 ans 大于等于0，就说明：有能够达到当前 average 的子区间方案，average 是可能是答案的。
6、对于 ans<0，则要变小 average，那么二分的区间就应往小的方向取；对于 ans>=0，则还可以变大 average 去尝试，区间往大的方向取。