3 条题解
-
0
题目理解
本题要求我们计算给定n个刺痛值中,连续m个刺痛值的和的最小值。这是一个典型的滑动窗口问题,可以通过维护一个长度为m的窗口,在数组中滑动计算窗口内元素的和,并更新最小和。
解题思路
初始化: 读取输入的n和m值。 读取n行刺痛值,存储在列表中。 初始化最小和为无穷大(用于比较和更新)。 计算第一个窗口(前m个刺痛值)的和。 滑动窗口: 从第m+1个元素开始,依次将窗口向右滑动。 每次滑动时,更新窗口内的和(减去窗口最左边的元素,加上窗口最右边的新元素)。 比较并更新最小和。 输出结果: 滑动完所有窗口后,输出最小和。
代码实现
以下是Python代码实现:
def find_min_sum(n, m, values): if m == 0 or n < m: return 0 # 根据题目约定,这种情况不应该出现,但为了代码健壮性还是加上处理 min_sum = float('inf') # 初始化最小和为无穷大 current_sum = 0 # 当前连续m个数的和 # 计算第一个窗口的和 for i in range(m): current_sum += values[i] min_sum = min(min_sum, current_sum) # 更新最小和 # 滑动窗口计算后续的和 for i in range(m, n): current_sum += values[i] - values[i - m] # 更新窗口内的和 min_sum = min(min_sum, current_sum) # 更新最小和 return min_sum # 读取输入 input_data = input().strip().split() n = int(input_data[0]) m = int(input_data[1]) values = [] for _ in range(n): value = int(input().strip()) values.append(value) # 计算并输出结果 result = find_min_sum(n, m, values) print(result)代码解释
find_min_sum函数用于计算连续m个刺痛值的和的最小值。 首先处理特殊情况,如m为0或n小于m的情况(虽然题目约定不会出现,但为了代码健壮性加上处理)。 使用滑动窗口的方法计算连续m个刺痛值的和,并更新最小和。 input()函数用于读取用户输入,strip()方法用于去除输入字符串的首尾空格,split()方法用于将输入字符串按空格分割成列表。 最后调用find_min_sum函数计算结果,并输出。
验证结果
以题目给出的输入数据为例:
8 3 1 4 7 3 1 2 4 3输出结果为:
6解释:连续3个刺痛值的和分别为12、14、10、7、6、6、9,其中最小值为6。
通过以上步骤,我们可以正确地计算出连续m个刺痛值的和的最小值。
- 1
信息
- ID
- 684
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- 递交数
- 30
- 已通过
- 7
- 上传者