[数据结构与算法]牛客2021暑期训练4-J-Average

牛客2021暑期训练4-J-Average

题目链接

题意

给定 n*m 的矩阵，w[i][j]=a[i]+b[j]，求一个不小于 x * y 的子矩阵，其平均值最大
n,m,ai,bi≤10⁵

题解

假设我们要求的子矩阵为
$$tot=\sum _{i=x1}^{x2}\sum _{j=y1}^{y2}(a_i+b_j)=(y2?y1+1)?\sum _{i=x1}^{x2}{a}_i+(x2?x1+1)?\sum _{j=y1}^{y2}{b}_j$$
那么
$$ave=\frac{(y2?y1+1)?{\sum }_{i=x1}^{x2}{a}_i+(x2?x1+1)?{\sum }_{j=y1}^{y2}{b}_j}{(x2?x1+1)?(y2?y1+1)}=\frac{{\sum }_{i=x1}^{x2}{a}_i}{x2?x1+1}+\frac{{\sum }_{i=y1}^{y2}{b}_j}{y2?y1+1}$$
也就是说，我们只需对 a 数组求连续且长度不小于 x 的最大平均值，b数组同理，接下来关键怎么求最大值
显然可以考虑单调性。假设 q 中为单减的平均值，遍历一个 i 可以弹出 q 末尾小于以 i 为结尾长度为 x 的平均值，以维护单调性，可以证明 q 前面的平均值加上一段相同的值仍是单减的

DB Ave(int l,int r)
{
	return (sum[r]-sum[l-1])/(DB)(r-l+1);
}

for(int i=x;i<=n;i++)
{
	while(0<=t&&Ave(q[t],i)<Ave(i-x+1,i)) t--;
	q[++t]=i-x+1;
	ans1=max(ans1,Ave(q[0],i));
}

代码

#include<bits/stdc++.h>
#define LL long long
#define DB double
using namespace std;
const int N=1e5+9;
int n,m,x,y,t;
DB ans1,ans2;;
int q[N];
DB a[N],sum[N];
DB Ave(int l,int r)
{
	return (sum[r]-sum[l-1])/(DB)(r-l+1);
}
int main()
{
	cin>>n>>m>>x>>y;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	t=-1;
	for(int i=x;i<=n;i++)
	{
		while(0<=t&&Ave(q[t],i)<Ave(i-x+1,i)) t--;
		q[++t]=i-x+1;
		ans1=max(ans1,Ave(q[0],i));
	}
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	t=-1;
	memset(q,0,sizeof(q));
	for(int i=y;i<=m;i++)
	{
		while(0<=t&&Ave(q[t],i)<Ave(i-y+1,i)) t--;
		q[++t]=i-y+1;
		ans2=max(ans2,Ave(q[0],i));
	}
	printf("%.10lf",ans1+ans2);
	return 0;
}