Average

题目大意

题目等价为：给定两个分别由n和m个数的序列a，b。分别找出长度不少于x和y的连续序列，使它们的平均值之和最大。

思路

寻找长度不少于x且满足某些条件的题目，是属于那些便于验证，暗示难以直接求出答案的题，所以可以去二分。

对于每次二分出来的可能结果，我们把序列全体减去这个数，然后问题就成为了是否存在一个长度不小于x，且其和大于0的连续序列。

在验证过程中，我们可以先求出来新的数组的前缀和$sum$​​，假如我们想要寻找长度不小于L的，我们当前验证到了第$i$​​ 位($i >= L$​​)，那么当前能够取得的最大值，显然就是当前 $sum[i] - min{sum[j]}$​​ ，其中$1\le j\le i - L$​​ 。所以我们只用不断维护当前得$min{sum[j]}$​​，并且用当前得到的值取更新$ans$​​，即$ans=max{sum[i] - min{sum[j]},ans}$​。最后判断$ans$​是否不小于0。

#include <iostream>
#include <cstdio>
using namespace std;

const int maxN = 1e5 + 6;
int n, m, x, y;
double a[maxN], b[maxN], ans, tmp[maxN], sum[maxN];

bool judge(double num[], int n, int needLength, double x)
{
    double ans = -1e10, minVal = 1e10;
    for(int i = 1; i <= n; ++i) {
        tmp[i] = num[i] - x;
        sum[i] = sum[i - 1] + tmp[i];
    }
    for(int i = needLength; i <= n; ++i) {
        minVal = min(sum[i - needLength], minVal);
        ans = max(ans, sum[i] - minVal);
    }
    return ans >= 0;
}

int main()
{
    double l = 0, r = 0;
    scanf("%d%d%d%d", &n, &m, &x, &y);
    for(int i = 1; i <= n; ++i) {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }
    for(int i = 1; i <= m; ++i)
        scanf("%lf", &b[i]);
    while(r - l > 1e-6) {
        double mid = (l + r) / 2;
        if(judge(a, n, x, mid))
            l = mid;
        else
            r = mid;
    }
    ans += l;
    l = 0, r = 1e5;
    while(r - l > 1e-7) {
        double mid = (l + r) / 2;
        if(judge(b, m, y, mid))
            l = mid;
        else
            r = mid;
    }
    ans += l;
    printf("%lf", ans);
    return 0;
}
 

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/08/05/Average/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！