刷题笔记合集🔗

问题描述

从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组,并输出其位置和大小。

几何平均值定义:K个数的几何平均值为这K个数乘积的K次方根。

若有多个子数组的几何平均值均为最大值:

1. 输出长度最小的子数组
2. 若长度相同,输出最前面的子数组

输入格式

第一行输入两个整数N、L:

• N表示数组大小(1 ≤ N ≤ 100000)
• L表示子数组最小长度(1 ≤ L ≤ N)

接下来N行,每行一个数字,表示数组元素(10^-9 ≤ numbers[i] ≤ 10^9)

输出格式

输出两个整数,用空格分隔:

• 第一个数表示子数组的起始位置(从0开始)
• 第二个数表示子数组的长度

备注

用例保证除最大几何平均值的子数组外,其他子数组的几何平均值至少比最大值小10^-10倍。

样例1

输入:

3 2
2
2
3

输出:

1 2

说明:

• 长度至少为2的子数组有:{2,2}、{2,3}、{2,2,3}
• {2,3}的几何平均值最大
• 所以输出起始位置1和长度2

样例2

输入:

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

输出:

2 2

说明:

• 有多个长度至少为2的子数组的几何平均值为0.2
• 其中长度最短的为2
• 长度为2且几何平均值为0.2的子数组中,最前面的是从位置2开始的两个0.2

题解

这道题目可以使用前缀积+排序的方法解决:

1. 计算前缀积数组dp,dp[i]表示nums[0]到nums[i]的乘积
2. 枚举所有可能的子数组:
   • 起始位置i从0到n-l
   • 结束位置j从i+l-1到n-1
   • 子数组乘积 = dp[j] / dp[i-1] (i>0时)
3. 对所有候选子数组排序:
   • 首先按几何平均值降序
   • 几何平均值相同时按长度升序
   • 长度相同时按起始位置升序
4. 输出排序后的第一个子数组的信息

时间复杂度: O(n^2 log n),其中n为数组长度

参考代码

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

class Avg:
    def __init__(self, start, root, fact):
        self.start = start  # 起始位置
        self.root = root    # 长度
        self.fact = fact    # 乘积
        self.avg = pow(fact, 1.0/root)  # 几何平均值

def cmp(a, b):
    # 比较几何平均值
    if abs(a.avg - b.avg) > max(a.avg, b.avg) / pow(10, 10):
        return 1 if b.avg - a.avg > 0 else -1
    # 长度相同比较位置
    if a.root != b.root:
        return a.root - b.root
    return a.start - b.start

# 计算前缀积
dp = [0] * n
dp[0] = numbers[0]
for i in range(1, n):
    dp[i] = numbers[i] * dp[i-1]

candidates = []

# 枚举所有可能的子数组
for i in range(n-l+1):
    for j in range(i+l-1, n):
        fact = dp[j] if i == 0 else dp[j]/dp[i-1]
        candidates.append(Avg(i, j-i+1, fact))

# 排序找出最优解
candidates.sort(key=lambda x: (-x.avg, x.root, x.start))

print(f"{candidates[0].start} {candidates[0].root}")

import java.util.*;

public class Main {
    static class Avg {
        int start;
        int root;
        double fact;
        double avg;