解题报告:二分平均值,由于他限定要不小于l长度的平均值,我们可以用个数组记录a[i]减去二分的平均值,如果最大的连续子序列长度大于等于0就l=mid ,由于是浮点数,eps设置为保留位数+2就行了,这题就是5.同时最后要乘以1000,l和r都是满足题意的,因为是最大值用r来*1000下取整就行了,接下来要找最大长度大于等于连续子序列的和,可以i从l开始循环,记录一下i-l前缀和和min,最后每次用前缀和i-min来更新ans就行了。
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define IL inline
#define x first
#define y second
typedef long long ll;
using namespace std;
const int N=1e5+10;
double a[N];
double sum[N];
double b[N];
int n ,L;
bool check(double mid)
{
double minv= 1e10;
double maxv=-1e10;
for(int i=L;i<=n;i++)
{
minv = min(minv,sum[i-L]);
maxv = max(maxv, sum[i]-minv);
}
return maxv>=0;
}
int main()
{
cin >> n >> L;
for(int i=1;i<=n;i++)
cin >> a[i];
double l =0 , r = 2000;
while(r-l>1e-5)
{
double mid =(l+r)/2;
for(int i=1;i<=n;i++)
b[i] =a[i] - mid;
for(int i=1;i<=n;i++)
sum[i] = sum[i-1] + b[i];
if(check(mid))
l = mid;
else
r=mid;
}
printf("%d\n",(int)((l+r)/2*1000));// 二分实数,取上界(当精确度小于题目精确度的时候L可以的时候R也必定可以,取大故取R)
return 0;
}