题解：average

最大平均值子序列

问题描述

给定一个长度为 (n) 的序列，求出序列中一段连续子序列的最大平均值，且这个连续子序列的长度不小于 (k)。要求输出保留 6 位小数的最大平均值。

输入描述：

• 第一行包含两个正整数 (n) 和 (k)。
• 第二行包含 (n) 个整数表示这个序列。

输出描述：

• 输出一个浮点数表示答案，保留 6 位小数。

示例1：

输入：

4 3 3 4 1 2

输出：

2.666667

示例2：

输入：

8 6 4 7 9 5 8 1 9 10

输出：

7.000000

备注：

• 对于 100% 的数据，满足 (k \leq n \leq 10^5)，且每个数 (a_i \leq 5000)。

解题思路

我们可以通过 二分查找 和 前缀和 技巧来高效地解决这个问题。

1. 二分查找:

• 我们的目标是找到一个子序列，其平均值最大，且长度不小于 (k)。
• 由于平均值是一个实数，我们可以通过二分查找来逼近最大平均值。
• 在每次的查找中，我们设定一个中值 (mid) 作为可能的最大平均值，然后判断是否存在一个连续子序列的平均值大于等于 (mid)。

2. 前缀和:

• 使用前缀和来快速计算任意子序列的和。
• 对于某个固定的 (mid)，我们将每个元素减去 (mid)，然后判断是否存在一个连续子序列，其和大于等于 0，且长度不小于 (k)。

3. 验证子序列是否满足条件:

• 在给定的 (mid) 值下，创建一个新的数组，数组中的每个元素为原数组的元素减去 (mid)。
• 然后，使用前缀和来检查是否存在一个长度至少为 (k) 的子数组，其和大于等于 0。

4. 终止条件:

• 使用二分查找，当区间的左右边界差小于一个精度值时，停止搜索，并输出当前的 (mid)。

代码实现

#include <bits/stdc++.h>
using namespace std;

bool canFind(const vector<int>& arr, int n, int k, double avg) {
    vector<double> sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + arr[i - 1] - avg;
    }
    double minSum = 0;
    for (int i = k; i <= n; ++i) {
        if (sum[i] - minSum >= 0) return true;
        minSum = min(minSum, sum[i - k + 1]);
    }
    return false;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    double l = -1e4, r = 1e4, res = 0;
    while (r - l > 1e-7) {  // 精度到达 1e-7
        double mid = (l + r) / 2;
        if (canFind(arr, n, k, mid)) {
            res = mid;
            l = mid;
        } else {
            r = mid;
        }
    }
    cout << fixed << setprecision(6) << res;
    return 0;
}