题解 | #Average#

J 题题解

浮点二分 ＋ 前缀和

思路

结论：对序列 a 求得最大的 平均值 res_a，再对序列 b 求得最大的 平均值 res_b，res_a + res_b 就是答案
res_a 的解释 及 求法

解释：
对于 序列 a 中 所有满足区间长度 大于或者等于 x 的 的区间
每个满足条件的区间 都有1个平均值 res_i (区间元素和 / 区间长度)
res_a = max(res_1,res_2,...,res_n)

求法：
第一想法：穷举每个满足条件的区间，更新最大平均值，但因为区间长度是至少为x ，而不是刚好为x
所以穷举的时间复杂度 是O(n^2)，显然会 T

第二想法：穷举每个平均值，找到最大的 且 满足条件的 平均值
因为平均值不是整数 没法 for(double i=0;i<=balabala;i++)
所以用 浮点数二分 “穷举”平均值

res_b 同理

解释：
对于 序列 b 中 所有满足区间长度 大于或者等于 y 的 的区间
每个满足条件的区间 都有1个平均值 res_i (区间元素和 / 区间长度)
res_b = max(res_1,res_2,...,res_n)

求法：浮点数二分 “穷举”平均值

关于 check 函数的解释

该题和 Acwing 102 最佳牛围栏 几乎一模一样，只不过这个是二维的 那个是一维的
但其实没啥区别 用两次浮点二分就行了 
所以，我在这就直接放上大佬写的 最佳牛围栏 这题的题解，里面对于check函数各种细节的解释 可谓经典

https://www.acwing.com/solution/content/1148/    orz

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

double a[N],b[N];
double sum[N];
double ans;
int n,m,x,y;

bool check1(double avg){
    memset(sum,0,sizeof sum);    
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+(a[i]-avg);

    double minm=1e9;
    for(int i=0,j=x;j<=n;i++,j++){
        minm=min(minm,sum[i]);
        if(sum[j]-minm>=0) return true;
    }
    return false;
}

bool check2(double avg){
    memset(sum,0,sizeof sum);    
    for(int i=1;i<=m;i++) sum[i]=sum[i-1]+(b[i]-avg);

    double minm=1e9;
    for(int i=0,j=y;j<=m;i++,j++){
        minm=min(minm,sum[i]);
        if(sum[j]-minm>=0) return true;
    }
    return false;
}

int main(){
    cin>>n>>m>>x>>y;
    for(int i=1;i<=n;i++)  cin>>a[i];
    for(int i=1;i<=m;i++)  cin>>b[i];

    double l=0,r=1e5+10;
    while(r-l>1e-8){  // 浮点二分
        double mid=(l+r)/2;
        if(check1(mid)) l=mid;
        else r=mid;
    }
    ans+=r;  // r 就是 res_a

    l=0,r=1e5+10;
    while(r-l>1e-8){
        double mid=(l+r)/2;
        if(check2(mid)) l=mid;
        else r=mid;
    }
    printf("%.10f\n",ans+r); // ans + r = res_a + res_b

    return 0;
}