2021牛客暑期多校训练营4
J. Average
题意:
在一个 n*m 的矩阵中选取子矩阵(最小为 x * y),求均值最大的子矩阵
分析:
根据题目对矩阵的描述,现取一个 x*y 的子矩阵,
average = (y * sum[xl, xr] + x * sum[yl, yr]) / xy = sum[xl, xr] / x + sum[yl, yr] / y;
所以,行列不会互相影响,最大化均值相当于分别求a、b两个数组的连续子区间的最大均值然后再求和。
连续子区间的最大均值用二分来求。
Code:
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
double a[N], s[N];
double binary(double *a, int n, int x)
{
double l=0, r=1e10;
// 二分求区间均值最大
while(r-l > 1e-9)
{
double mid = (l+r)/2;
for(int i=1;i<=n;i++)
{
s[i] = s[i-1]+a[i]-mid;
}
double mn = 1e9, mx = -1e9;
for(int i=x;i<=n;i++)
{
// 求区间和最大值
mn = min(mn, s[i-x]);
mx = max(mx, s[i]-mn);
}
if(mx > 0) l = mid;
else r = mid;
}
return l;
}
signed main()
{
ios_base::sync_with_stdio(false);
int n, m, x, y;
cin>>n>>m>>x>>y;
for(int i=1;i<=n;i++) cin>>a[i];
double ans=0;
ans += binary(a, n, x);
for(int i=1;i<=m;i++) cin>>a[i];
ans += binary(a, m, y);
cout<<fixed<<setprecision(10)<<ans;
return 0;
}