题解 | #Average#

题目描述：
简单来说就是给你两个数组，a和数组b。然后定义矩阵w[i][j]=a[i]+b[i]，在这个矩阵内找一个子矩阵得到，这个字矩阵内的平均值最大，这个子矩阵长不得小于x,宽不得小于y。
题目分析：
每个矩阵的平均值为:

又由于w[i][j]=a[i]+b[j]得子矩阵的和就等于

平均值就为

这样就可以吧题目分为分别找第一项的最大值与第二项的最大值的和，由于题目给的大小为1e5我们可以用二分来找最大值。

bool check(ll x,ll*v,int tx,int t)
{
    for(int i=1;i<=t;i++){
        ans[i]=v[i]+ans[i-1]-x;
    }
    ll mini=0;
    for(int i=tx;i<=t;i++){
        if(ans[i]-mini>=0)return 1;
        mini=min(mini,ans[i-tx+1]);
    }    
    return 0;
}
ll f(ll *v,int tx,int t）//二分答案
{
    ll l=0,r=1e9;
    for(int i=1;i<=1000;i++){
        ll mid=(l+r)/2;
        if(check(mid,v,tx,t))l=mid;
        else r=mid;
    }
    return l;
}

AC代码

#include<bits/stdc++.h>
#define ll double 
using namespace std;
const int N=1e5+20;
ll a[N],b[N],ans[N]={0};
bool check(ll x,ll*v,ll tx);
ll f(ll *v,int tx,int t);
int main()
{
    int n,m,x,y,i;
    cin>>n>>m>>x>>y;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=m;i++)cin>>b[i];
    printf("%.10lf\n",f(a,x,n)+f(b,y,m));
    return 0;
}
bool check(ll x,ll*v,int tx,int t)
{
    for(int i=1;i<=t;i++){
        ans[i]=v[i]+ans[i-1]-x;
    }
    ll mini=0;
    for(int i=tx;i<=t;i++){
        if(ans[i]-mini>=0)return 1;
        mini=min(mini,ans[i-tx+1]);
    }    
    return 0;
}
ll f(ll *v,int tx,int t)
{
    ll l=0,r=1e9;
    for(int i=1;i<=1000;i++){
        ll mid=(l+r)/2;
        if(check(mid,v,tx,t))l=mid;
        else r=mid;
    }
    return l;
}