「USACO 2003 Mar. Green」Best Cow Fences

发表于 | 分类于 ，

哎呀！图片走丢了！

题目描述

给定一个长度为 $n$ 的非负整数序列 $A$ ，求一个平均数最大的，长度不小于 $L$ 的子段。

输入格式

第一行用空格分隔的两个整数 $n$ 和 $L$；

第二行为 $n$ 个用空格隔开的非负整数，表示 $A_i$。

输出格式

输出一个整数，表示答案的 $1000$ 倍。不用四舍五入，直接输出。

样例输入
1
2
10 6
6 4 2 10 3 8 5 9 4 1
样例输出
1
6500
数据范围与提示

$1≤n≤10^5, 0≤A_i≤2000$。

解答

读完题发现这道题让我们求出一个最大的平均数，而这个平均数大概在一个区间内，所以考虑二分答案，并判定”是否存在一个长度不小于L的子序列，平均数不小于二分的值“。

那么如何判断平均数是否小于二分的值呢？如果一个序列的平均值是二分的值，那么这个序列的每个数减去平均值后再加在一起和一定等于0，如果一个序列的平均值小于二分的值，那么减完后的和一定大于0。所以我们只要判定“是否存在一个长度不小于L的子序列，子序列的和非负”

现在我们只需要考虑如何求一个子序列，它的和最大，且长度不小于L。

我们知道子序列的和可以转化为前缀和相减的形式，所以我们设$sum_i$表示$A_1～A_i$的和，则有：

观察式子可以发现，随着$i$的增加，$j$的取值范围每次只会增加$1$。也就是说，集合$min\{sum_j\}$中每次只会增加一个新的取值，所以我们不用每次$i$递增时都循环枚举$j$次，只需要记录当前最小值，每次与新的$sum_{i-L}$取$min$即可。

解决了这个问题，我们只需要判断最大的子序列和是否非负，就可确定当前二分的值是否正确了。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100010;
double a[maxn],b[maxn],add[maxn];
int n,len;
int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>len;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	double l=-1e6,r=1e6,eps=1e-5;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		for(int i=1;i<=n;i++)
			b[i]=a[i]-mid;
		for(int i=1;i<=n;i++)
			add[i]=add[i-1]+b[i];
		double minn=1e10,ans=-1e10;
		for(int i=len;i<=n;i++)
		{
			minn=min(minn,add[i-len]);
			ans=max(ans,add[i]-minn);
		}
		if(ans>=0)
			l=mid;
		else
			r=mid;
	}
	cout<<int(r*1000)<<endl;
	return 0;
}
0%