子序列的平均值

题目连接：http://poj.org/problem?id=2018

题目描述

给定一个长度为n的非负序列A，请你找出一个长度不小于L的子段（子段是序列A中一些连续的元素构成的集合），使得子段中数值的平均值最大。最终输出这个最大的平均值。

输入描述

第一行两个整数n,L(1<=L<=n<=100,000)
以下n行，每行一个非负整数，表示序列A中每个元素的值。

输出描述

一个整数，欲求的最大平均值乘以1000后的结果（注意不要四舍五入，直接输出）。

示例

输入

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

输出

6500

分析

二分思路

可以通过二分答案的方法来做，一组数据的平均值一定在该组数据的最大值和最小值之间，那么我们可以通过二分法获得中间的数字mid，再判断是否有一组长度不小于L的子数组的平均值为mid。

怎么判断子数组的平均值是否是mid，可以先让每个数字减去mid，然后再看是否有一组长度不小于L的子数组的和大于等于0，如果有，那么说明该子数组的平均值要大于mid，这样一来二分就可以进行下去了，平均值大于mid，那么就要让二分法左边的值为mid，如果没有任何一组长度不小于L的子数组的和大于等于0，那么说明平均值肯定要小于mid，这时候就要让二分法右边的值为mid。

总体思路如上，但还有两个关键问题：

1. 是否存在一组长度不小于L的子数组的和大于等于0
2. 二分得精度应该取多少，达到精度后怎样处理

存在长度限制的最大连续子序列和

若不能存在长度限制，则可以通过动态规划求解。

记a[i]为第i个数的值，f[i]为以第i个数结尾的最大连续子序列和，则状态转移方程如下：
f[i]=max(a[i],a[i]+f[i])

若存在长度限制L，要求子序列的长度不小于L，则需要变更方法。

字段和可以转化成为前缀和相减的形式，也就是说sum[i] = (a[1] + a[2] + … + a[i])，因此：
max(i-j>=L){a[j]+a[j+1]+…+a[i]} = max(L<=i<=n){sum[i]-min(0<=j<=i-L){sum[j]}}

仔细观察上式子，随着i的增长，j的取值范围0~i-L每次只会增大1.换言之，每次只会有一个新的取值进入min{sumj}的候选集合，所以我们没有必要每次循环枚举j ,只需要用一个变量记录当前最小值，每次与新的取值sum(i-L)取min就可以了。

二分答案的处理

二分法可以保证我们离最优解的误差小于我们设定的误差，但题目要求输出最优解的前几位有效数字，两者不等价（无论精度取多少）。

该题没有较好的解决办法，经实验，精度控制在1e-5内，直接取上界处理可以通过，但如果数据刁钻，二分法其实没有办法保证前几位数字与最优解一致。

AC代码

---

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 100005;
int n, L;
int v[N];
double sum[N];

int main()
{
	cin >> n >> L;
	double l = 0, r = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
		r = max(r, double(v[i]));
	}
	sum[0] = 0;
	while (r - l > 1e-5)
	{
		double mid = (l + r) / 2;
		for (int i = 1; i <= n; i++)
			sum[i] = sum[i - 1] + v[i] - mid;
		double mins = 1e9;
		bool isExisted = false;
		for (int i = L; i <= n; i++)
		{
			mins = min(mins, sum[i - L]);
			if (sum[i] - mins > 0)
			{
				isExisted = true;
				break;
			}
		}
		if (isExisted)
			l = mid;
		else
			r = mid;
	}
	cout << int(r * 1000) << endl;
	return 0;
}