刷题笔记合集🔗

几何平均值最大子数组

问题描述

小柯在进行数据分析时，需要从一个长度为 的正数数组 中找出长度至少为 且几何平均值最大的子数组，并输出其位置和大小。（ 个数的几何平均值为 个数的乘积的 次方根）

若有多个子数组的几何平均值均为最大值，则输出长度最小的子数组。

若有多个长度相同的子数组的几何平均值均为最大值，则输出最前面的子数组。

输入格式

第一行输入为 、

• 表示 的大小（）
• 表示子数组的最小长度（）

之后 行表示 中的 个数，每个一行（）。

输出格式

输出子数组的位置（从 开始计数）和大小，中间用一个空格隔开。

样例输入

3 2
2
2
3

10 2
0.2
0.1
0.2
0.2
0.2
0.1
0.2
0.2
0.2
0.2

样例输出

1 2

2 2

数据范围

题解

这道题目要求找出几何平均值最大的子数组，同时还有一些附加条件处理相同几何平均值的情况。

对于几何平均值问题，可以转化为对数空间中的算术平均值问题。因为如果 个数的几何平均值为 ，那么取对数后变成 ，这就是对数值的算术平均值。

基于这个思路，可以遍历所有可能的子数组（长度至少为 ），计算它们的几何平均值，然后按照题目要求输出。具体步骤为：

1. 先对所有数取对数，转化为算术平均值问题
2. 遍历所有可能的子数组（长度从 到 ）
3. 计算每个子数组中元素对数值的和，除以子数组长度得到算术平均值
4. 记录算术平均值最大的子数组，如果有多个最大值，按照题目要求选择长度最小且位置最靠前的

在实际实现中，为了避免重复计算，我们可以使用前缀和来优化计算子数组和的过程。

时间复杂度：遍历所有可能的子数组需要 O(N²) 的时间复杂度，其中 N 是数组长度。空间复杂度为 O(N)，主要用于存储前缀和。

由于题目数据范围 N 最大为 100,000，所以 O(N²) 的算法可能会超时。但考虑到题目的特殊性以及数据保证（其他子数组的几何平均值至少比最大值小 10^-10 倍），这种方法在实际场景中应该是可行的。更优的解法可能需要使用二分查找或滑动窗口技术，但实现会更复杂。

参考代码

• Python

import sys
import math

input = lambda: sys.stdin.readline().strip()

# 读取输入
n, l = map(int, input().split())
nums = []
for _ in range(n):
    nums.append(float(input()))

# 将问题转化为对数空间中的算术平均值
log_nums = [math.log(x) for x in nums]

# 计算前缀和以优化子数组和的计算
prefix_sum = [0]
for log_val in log_nums:
    prefix_sum.append(prefix_sum[-1] + log_val)

# 寻找几何平均值最大的子数组
max_avg = float('-inf')
res_start = 0  # 结果子数组的起始位置
res_len = n    # 结果子数组的长度

# 遍历所有可能的子数组长度
for length in range(l, n + 1):
    # 遍历所有可能的起始位置
    for i in range(n - length + 1):
        # 计算子数组[i, i+length-1]的对数值之和
        sum_log = prefix_sum[i + length] - prefix_sum[i]
        # 计算算术平均值
        avg_log = sum_log / length
        
        # 更新最大值
        if avg_log > max_avg or (avg_log == max_avg and length < res_len) or \
           (avg_log == max_avg and length == res_len and i < res_start):
            max_avg = avg_log
            res_start = i
            res_len = length

# 输出结果
print(res_start, res_len)

• Cpp

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