-
题目：Average
-
题意：给出两个序列a、b，定义一个矩阵w，w[i][j] = a[i] + b[j]，求该矩阵中宽至少为x，长至少为y的子矩阵元素之和的平均值最大能为多少。
-
思路：二分 + 前缀和（与最佳牛围栏相似）
-
解析：经过公式推导可得：
不难发现，此时需要求+号两边的式子最大值即可得到Avg的最大值，实际上就是找出a序列中平均值最大的一段（平均值为avgA）与b序列中平均值最大的一段（平均值为avgB）之和即为答案。举例avgA二分求解过程（avgB同理可得）：
\[\begin{align} &\sum_{i=l_1}^{r1}ai/(r_1-l_1+1)\geq avgA \\ &\sum_{i=l_1}^{r1}a_i \geq avgA\times(r_1-l_1+1) \\ &\sum_{i=l_1}^{r1}a_i-avgA\geq0 \end{align} \] 接着利用前缀和+双指针来寻找是否存在一段子段和满足上诉条件，使得该字段和-枚举的平均值avgA*（子段和元素个数）>= 0的情况出现，在这里重点写一下之前第一次写最佳牛围栏的时候的疑惑：
在代码中的sum[i]实际上不一定保证随着i增大而增大，因为二分枚举的平均值avg可能比该子段中任意一个数大，但是为了保证该子段至少有x/y个数，那么我们需要设置一个双指针i, j（i为前指针从0开始，j为后指针从x/y开始）然后记录前指针扫描过的最小值minV，这样后指针j扫描的值sum[j]-minV肯定保证该子段长度至少为x/y，并且可以找到所有子段中平均值最大tempAvg的那个子段（j一直遍历到序列最后一个元素），若tempAvg > avg，则二分的区间可以往右区间缩小（枚举更大的avg）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, m;
double sum[N];
int check(double t[], double avg, int len, int num)
{
double minV = 0x3f3f3f3f;
for(int i = 1; i <= len; i++) sum[i] = sum[i-1] + t[i] - avg;
for(int i = 0, j = num; j <= len; i++, j++)
{
minV = min(minV, sum[i]);
if(sum[j] - minV >= 0) return 1;
}
return 0;
}
double solve(double t[], int len, int num)
{
double l = 0, r = 1e6;
for(int i = 1; i <= 100; i++)
{
double mid = (l + r) / 2;
if(check(t, mid, len, num)) l = mid;
else r = mid;
}
return l;
}
int main()
{
double a[N], b[N];
int x, y;
cin >> n >> m >> x >> y;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) cin >> b[i];
double res = solve(a, n, x) + solve(b, m, y);
printf("%.10lf\n", res);
return 0;
}