北语 12.6Unaverage 2

点击查看代码

#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=1e5+10;
int n,k;
LL a[N],b[N],s[N];bool check(LL x)
{//预处理前缀和数组for(int i=1;i<=n;i++){b[i]=a[i]*1000-x;s[i]=s[i-1]+b[i];}LL mn=0;for(int i=k;i<=n;i++){mn=min(mn,s[i-k]);if(s[i]-mn>=0) return true;}return false;
}int main()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++) scanf("%lld",&a[i]);LL l=0,r=1e12,mid,ans;while(l<=r){LL mid=l+r>>1;if(check(mid)) l=mid+1,ans=mid;else r=mid-1;}cout<<ans;return 0;
}

一道非常棒的题目，考察了前缀和二分 对思维的考察很深入 首先，题目要求在长度为n的数组中找到长度大于等于k的平均值最大的片段，我们可以假设平均值x，然后对数组的每一个元素都减去x,这样看一个片段的和是否大于0就可知他们的平均值是否大于x，问题就转化为了求片段和，可以用前缀和 其次，如何搜索长度大于等于k的片段和最大片段，我们可以从左右端点的角度考虑，固定右端点用来遍历。动态维护一个左端点，我们要让一个片段和最大就是s[j]-s[i-1]最大，那么左端点s[i-1]就是越小越好，我们在遍历右端点的过程中可以顺便维护左端点的最小性，用min（mn，s[i-k])即可 最后，我们二分查找答案即可，因为l=r的时候我们还要对ans的值做操作，l，r不是直接返回值（好像也可以。。。不过还是养成好习惯 话外，二分直接满足向下取整了，不用再考虑了，因为实际值就是较小值啊