27141: 完美的爱

http://cs101.openjudge.cn/practice/27141/

一天，小帅和小美来到一处世外桃源，映入眼帘的是岛主为二人准备好的n个礼物，排成一排。但是岛主说他们只能选一部分的礼物带走，具体规则如下 :

如果他们能从这n个礼物中选出连续相邻的若干个礼物，且这些礼物的平均价值是520，那么他们就可以带走这些礼物。

那么问题来了，他们这次能带走总价值最多为多少的礼物呢。

输入

第一行为一个正整数n，n<10^5 第二行为n个整数，表示每个礼物的价值

输出

总价值(整数 )

样例输入

10
520 521 519 12 124 512 520 519 518 522

样例输出

来源

2023 课程微信群

超时代码

python

def find_max_value(n, gifts):
    prefix_sum = [0] * (n + 1)
    for i in range(n):
        prefix_sum[i + 1] = prefix_sum[i] + gifts[i]

    max_value = 0
    for i in range(n):
        for j in range(i + 1, n + 1):
            subarray_sum = prefix_sum[j] - prefix_sum[i]
            subarray_length = j - i
            if subarray_sum / subarray_length == 520:
                max_value = max(max_value, subarray_sum)

    return max_value

# 读取输入
n = int(input())
gifts = list(map(int, input().split()))

# 计算结果
result = find_max_value(n, gifts)
print(result)

为了使用滑动窗口优化这段代码，我们需要改变策略来寻找平均值为520的子数组。原始代码中嵌套循环的时间复杂度是O(n^2)，这在处理大量数据时会非常慢。我们可以通过维护一个滑动窗口，并且只遍历一次数组（线性时间）来优化它。

但是，对于这个问题来说，直接应用传统的滑动窗口并不合适，因为我们要找的是一个平均值等于特定值的连续子数组，而不是简单的最大或最小和。这里的关键在于转换问题：我们可以将原问题转化为求解前缀和的问题，然后利用哈希表存储已经访问过的前缀和及其对应的索引，从而快速判断是否存在满足条件的子数组。

下面是优化后的代码实现：

python

from collections import defaultdict

def find_max_value(n, gifts):
    target_average = 520
    # 计算需要的偏移量使得目标变为0
    gifts_offset = [x - target_average for x in gifts]

    prefix_sum = 0
    max_length = 0
    sum_indices = defaultdict(list)
    sum_indices[0].append(-1)  # 初始化，表示从开始到-1的和为0

    for i, gift in enumerate(gifts_offset):
        prefix_sum += gift
        if prefix_sum in sum_indices:
            # 如果当前前缀和之前出现过，说明存在一个子数组其元素平均值为target_average
            length = i - sum_indices[prefix_sum][0]  # 取最早的索引来获得最长的子数组
            max_length = max(max_length, length)
        sum_indices[prefix_sum].append(i)

    # 计算最大子数组的总和
    max_value = max_length * target_average if max_length > 0 else 0
    return max_value


# 读取输入
n = int(input())
gifts = list(map(int, input().split()))

# 计算结果
result = find_max_value(n, gifts)
print(result)

gifts_offset：将每个礼物的价值减去目标平均值520，这样做的目的是让目标变成找到一个和为0的子数组。
prefix_sum：这是从前到当前位置所有元素的累积和。
sum_indices：这是一个字典，用来记录每个前缀和第一次出现的位置。如果同一个前缀和再次出现，则意味着在这两个位置之间的子数组的平均值就是目标平均值。
max_length：用于跟踪最长的有效子数组长度。
max_value：最后计算的最大子数组的总和。
这种方法确保了算法能够在O(n)时间内完成，极大地提高了效率。请注意，这里的max_value实际上是基于max_length和target_average计算得出的，因为真正关心的是最长的子数组，而不是具体的数值总和。

27141: 完美的爱 ​

27141: 完美的爱