题目链接

题目大意

给两不一定等长的数组 a，b，我们用公式 c[i][j] = a[i] + b[j] 得到二维数组 c
找到该二维数组中 a 方向长度至少为 x，b 方向长度至少为 y 的一个连续子矩阵，使该子矩阵的数的均值最大

解题思路

不难发现对于一个长为x宽为y的子矩形而言

sum=\Sigma_{i}^{i+x}\Sigma_{j}^{j+y} c[i][j]

avg=\dfrac{sum}{xy}=\dfrac{\Sigma_{i}^{i+x}\Sigma_{j}^{j+y} c[i][j]}{xy}

利用c[i][j]=a[i]+b[j]拆分公式，可得：

sum=y\Sigma_{i}^{i+x} a[i] + x\Sigma_{j}^{j+y} b[j]

avg=\dfrac{sum}{xy}=\dfrac{y\Sigma_{i}^{i+x} a[i] + x\Sigma_{j}^{j+y} b[j] }{xy}

avg=\dfrac{\Sigma_{i}^{i+x} a[i] }{x}+\dfrac{\Sigma_{j}^{j+y} b[j] }{y}

avg=\bar a_i + \bar b_j

因此，问题转化为求两个数组的最大子段平均值

关于计算请参考另外一篇文章最大子段平均数

于参考文章不同，本题需要对实数范围内进行二分，所以会在原代码的基础上进行改动，请参考下方的代码实现

代码实现

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+7;
const double eps = 1e-10;
const int inf = 1e10;
const int mod = 1e9+7;
int T;
int n,m,x,y;
double a[N],b[N];
double sum[N];
double ans,ans1,ans2;
double minn;

bool check1(double mid){//对a数组进行check
    for (int i=1;i<x;i++) sum[i]=sum[i-1]+(a[i]-mid);
    minn=inf;
    for (int i=x;i<=n;i++){
        sum[i]=sum[i-1]+(a[i]-mid);
        minn=min(minn,sum[i-x]);
        if(sum[i]>minn){
            return 1;
        }
    }
    return 0;
}
bool check2(double mid){//对b数组进行check
    for (int i=1;i<y;i++) sum[i]=sum[i-1]+(b[i]-mid);
    minn=inf;
    for (int i=y;i<=m;i++){
        sum[i]=sum[i-1]+(b[i]-mid);
        minn=min(minn,sum[i-y]);
        if(sum[i]>minn){
            return 1;
        }
    }
    return 0;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    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;
    double mid=(l+r)/2;
    while(r-l>eps){//对a数组进行二分
        mid=(l+r)/2;
        if (check1(mid))l=mid;
        else r=mid;
    }       
    ans1=mid;
    l=0,r=1000000;
    mid=(l+r)/2;
    while(r-l>eps){//对b数组进行二分
        mid=(l+r)/2;
        if (check2(mid))l=mid;
        else r=mid;
    }     
    ans2=mid;
    ans=ans1+ans2;
    printf("%.10f",ans);
    return 0;
}