题意:给你两个长度分别\(n\)和\(m\)的序列\(a\)和\(b\),构造一个\(n\)x\(m\)的矩阵,每个单位的权值\(w_{i,j}=a_i+b_j\),现在要选一个长宽至少为\(x\)x\(y\)的子矩阵,求所选矩阵的最大平均值.

题解:这题不难转化为在\(a\)中找长度最小为\(x\)的区间最大平均值和在\(b\)中找长度最小为\(y\)的区间最大平均值,二者的和就是答案.但是这个\(x\)和\(y\)是变化的,并不好找.不妨假设\(a\)的最大平均值为\(A\),先不管区间长度是多少,只要合法就行,那么一定有\((a[i]+...+a[j])/len=A\ (len\ge x)\),整理一下可得:\((a[i]-A)+...+(a[j]-A)=0\).这里可以发现这个式子是具有单调性的,只要\((a[i]-A)+...+(a[j]-A)=\ge 0\)即可.那么我们就可以二分平均值来求,用前缀和来求区间值,同时维护左区间前缀和最小值就能求出动态区间的最大值.具体看代码会更容易理解一些.

代码:

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define me memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
const int N = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using namespace std;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

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

int main() {
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m>>x>>y;
    rep(i,1,n) cin>>a[i];
    rep(i,1,m) cin>>b[i];

    double l=-1e9,r=1e9;
    while(r-l>1e-6){
        double mid=(l+r)/2;
        rep(i,1,n){
            pre[i]=pre[i-1]+a[i]-mid;
        }
        double mi=1e9;
        double mx=-1e9;
        rep(i,x,n){
            mi=min(pre[i-x],mi);
            mx=max(pre[i]-mi,mx);
        }
        if(mx>0) l=mid;
        else r=mid;
    }
    double res1=l;
    l=-1e9,r=1e9;
    while(r-l>1e-7){
        double mid=(l+r)/2;
        rep(i,1,m){
            pre[i]=pre[i-1]+b[i]-mid;
        }
        double mi=1e9;
        double mx=-1e9;
        rep(i,y,m){
            mi=min(pre[i-y],mi);
            mx=max(pre[i]-mi,mx);
        }
        if(mx>0) l=mid;
        else r=mid;
    }
    double res2=l;
    cout<<fixed<<setprecision(10)<<res1+res2<<'\n';

    return 0;
}