牛客2021暑期训练4-J-Average
题意
给定 n*m 的矩阵，w[i][j]=a[i]+b[j]，求一个不小于 x * y 的子矩阵，其平均值最大
n,m,ai,bi≤105
题解
假设我们要求的子矩阵为
t
o
t
=
∑
i
=
x
1
x
2
∑
j
=
y
1
y
2
(
a
i
+
b
j
)
=
(
y
2
?
y
1
+
1
)
?
∑
i
=
x
1
x
2
a
i
+
(
x
2
?
x
1
+
1
)
?
∑
j
=
y
1
y
2
b
j
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
tot=i=x1∑x2?j=y1∑y2?(ai?+bj?)=(y2?y1+1)?i=x1∑x2?ai?+(x2?x1+1)?j=y1∑y2?bj?
那么
a
v
e
=
(
y
2
?
y
1
+
1
)
?
∑
i
=
x
1
x
2
a
i
+
(
x
2
?
x
1
+
1
)
?
∑
j
=
y
1
y
2
b
j
(
x
2
?
x
1
+
1
)
?
(
y
2
?
y
1
+
1
)
=
∑
i
=
x
1
x
2
a
i
x
2
?
x
1
+
1
+
∑
i
=
y
1
y
2
b
j
y
2
?
y
1
+
1
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}
ave=(x2?x1+1)?(y2?y1+1)(y2?y1+1)?∑i=x1x2?ai?+(x2?x1+1)?∑j=y1y2?bj??=x2?x1+1∑i=x1x2?ai??+y2?y1+1∑i=y1y2?bj??
也就是说，我们只需对 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;
}