前缀和 + 二分
- 枚举答案avg 如果存在符合的序列满足要求 l = avg 否则 r = avg
- 对于当前的avg而言,要找到长度 >= F的连续序列 可以考虑 利用前缀和。一种优化的枚举方式是,将区间按照右端点分类,枚举右端点。
- 又考虑到,对于右端点k,只需找到左侧的最小值。而对于最小值而言,可以用一个变量存储。
写的好乱啊。。。代码很精妙,完整描述需要铺垫好多~
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int n,F;
double a[maxn],s[maxn];
bool check(double avg)
{
for(int i = 1;i <= n;i++) s[i] = s[i - 1] + a[i] - avg;
double mins = 0; //记录区间
for(int k = F;k <= n;k++) //枚举区间右端点
{
mins = min(mins,s[k - F]); //记录最小值
if(s[k] >= mins) return true;
}
return false;
}
int main()
{
cin >> n >> F;
double l = 0,r = 0;
for(int i = 1;i <= n;i++) scanf("%lf",&a[i]),r = max(a[i],r);
while(r - l > 1e-5)
{
double mid = (l + r) / 2;
if(check(mid)) l = mid;
else r = mid;
}
cout << (int)(r * 1000);
return 0;
}