2021牛客暑期多校训练营4 J.Average (二分答案,前缀和维护动态区间)

2021牛客暑期多校训练营4 J.Average (二分答案,前缀和维护动态区间)

  • 题意:给你两个长度分别\(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;
    }
    
    
上一篇:无向图的最小环问题


下一篇:傻逼的自我修养