描述:
(给一个长度为 n 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 ≥m。)
题目传送门:平均数
题目算法:二分+DP+思维
分割线
又是束手无策的一道题目，理解起来也很反人类.......以下见解摘自这位dalao
Ⅰ.如何进行二分
二分最大平均值，然后进行验证。如何验证？将序列中的元素减去平均值
如果有一段长度不小于L的区间和大于等于0，说明该平均值可行，调整边界，继续二分。
Ⅱ.如何求有限制性最大子段和
方法1
求一个子段，它的和最大，没有“长度不小于L”这个限制。这个可以用动态规划解决。 (d[i]=max(d[i-1]+A[i],0.0));
(d[i])为以i结尾的最大子段和
如何将“限制性”转化为一般情况：
设(s[i])为以i结尾且长度不小于L的最大子段和，(A[i])为原数组，(sum[i])为前缀和。
因为长度要不小于L,所以从(A[i-L])一直到(A[i])是必选的，总和为(sum[i]-sum[i-L]),前面(i-L)个数可选可不选
要想和最大，就要加上以(a[i-L])结尾的最大子段和，所以(s[i]=sum[i]-sum[i-L]+d[i-L]) (前面(i-L)个数的最大子段和)
最后在(s[i])中取一个最大值就是(ans)。也可以不用s数组，直接在过程中取最大值
方法2
最大子段和可以转化为前缀和相减的形式。
设sum[i]为序列A的前i项的和 ，设s[i]是序列A以A[i]结尾且长度不小于L的最大连续子段和
那么显然有: (s[i] = sum[i] - min){(sum[j])}((0<=j<=i-L))
这里的代码用的是第一种方法。
#include <bits/stdc++.h>
using namespace std;
const int maxn=100009;
const double eps=1e-7;
int n,m;
double a[maxn],b[maxn],dp[maxn],sumn[maxn];
bool check(double mid)
{
for(int i=1;i<=n;i++)
{
b[i]=a[i]-mid;
sumn[i]=sumn[i-1]+b[i];
dp[i]=max(dp[i-1]+b[i],0.0);
}
for(int i=m;i<=n;i++)
if(dp[i-m]+sumn[i]-sumn[i-m]>=0) return true;
return false;
}
int main()
{
scanf("%d%d",&n,&m);
double l=0,r=0,mid;
for(int i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
r=max(r,a[i]);
}
while(r-l>eps)
{
mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
printf("%d",int(r*1000));
}