问题描述

Farmer John的农场由一排$N$（$1 \leq N \leq 100,000$）块田地组成。每块田地里有一定数量的奶牛，$1 \leq \text{奶牛数量} \leq 2000$。

FJ想要在一块连续的田地周围建一个围栏，以使得该区域内每块田地的平均奶牛数量最大化。这个区域必须包含至少$F$（$1 \leq F \leq N$）块田地，其中$F$是给定的输入。

在给定的约束条件下，计算围栏的放置位置，使得平均奶牛数量最大化。

输入

• 第$1$行：两个用空格分隔的整数，$N$和$F$。
• 第$2..N+1$行：每行包含一个整数，表示一块田地里的奶牛数量。第$2$行给出第$1$块田地的奶牛数量，第$3$行给出第$2$块田地的奶牛数量，以此类推。

输出

• 第$1$行：一个整数，表示最大平均值的$1000$倍。不要进行四舍五入，只需打印出$1000 \times \frac{\text{奶牛数量}}{\text{田地数量}}$的整数部分。

示例

输入：

10 6
6 
4
2
10
3
8
5
9
4
1

输出：

6500

解题思路

为了高效地解决这个问题，我们可以采用二分搜索结合前缀和的方法。具体步骤如下：

1. 确定平均值的范围：由于每块田地的奶牛数量在$1$到$2000$之间，平均值的可能范围也是$1$到$2000$。
2. 二分搜索：在$1$到$2000$之间进行二分搜索，寻找最大的平均值$mid$，使得存在一个长度至少为$F$的连续子数组，其平均值至少为$mid$。
3. 检查可行性：对于每个$mid$，计算前缀和数组$prefix$，其中$prefix[i] = prefix[i-1] + (\text{cows}[i] - mid)$。然后检查是否存在一个长度至少为$F$的子数组，其和$\geq 0$。
4. 维护最小前缀和：为了高效检查，维护一个$min\_prefix$，表示前$i-F$个$prefix$的最小值。如果$prefix[i] - min\_prefix \geq 0$，则存在满足条件的子数组。
5. 输出结果：最终的最大平均值乘以$1000$并取整，即为所求。

解决代码

#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
using namespace std;
const double dlt=1e-5;
int n,L;
double a[100007],b[100007],pre[100007];
int main() {
	scanf("%d%d",&n,&L);
	for(int i=1; i<=n; i++) {
		scanf("%lf",&a[i]);
	}
	double l=-1e6,r=1e6;
	while(r-l>dlt) {
		int k=0;
		double mi=(l+r)/2;
		double mins=1e10;
		for(int i=1; i<=n; i++) {
			b[i]=a[i]-mi;
		}
		for(int i=1; i<=n; i++) {
			pre[i]=pre[i-1]+b[i];
		}
		for(int i=L; i<=n; i++) {//一边找最小的前缀和，一边进行运算；这个也关键！
			mins=min(pre[i-L],mins);
			if(pre[i]-mins>=0) {
				k=1;
				l=mi;
				break;
			}
		}
		if(!k)
			r=mi;
	}
	r=r*1000;
	printf("%d\n",(int)r);
	return 0;
}