简易题解
题目大意
给定 \(n\) 个正整数，称为“刺痛值”，以及一个整数 \(m\)。我们需要找出所有连续的 \(m\) 个刺痛值之和的最小值。
思路分析
题目要求我们找到长度为 \(m\) 的连续子数组（子序列）的和的最小值。
由于 \(n\) 的最大值为 \(3 \times 10^3\)，我们可以采用以下几种方法：
-
暴力枚举（Two Pointers / Sliding Window 简化版）：
最直观的方法是，从第一个可能的连续 \(m\) 个刺痛值序列开始，计算其和。然后依次向后移动，每次都计算一个新的连续 \(m\) 个刺痛值序列的和，并与当前记录的最小值进行比较。- 设一个变量
min_sum存储目前找到的最小和，初始化为一个足够大的值（例如，所有刺痛值都取最大值100，m最大3000，则100 * 3000 = 300000，所以300001是一个安全的初始大值）。 - 外层循环
i从 \(1\) 遍历到n - m + 1，表示连续 \(m\) 个刺痛值序列的起始位置。 - 内层循环
j从i遍历到i + m - 1，计算当前以a[i]为起点，长度为 \(m\) 的子序列的和current_sum。 - 每次计算完
current_sum后，与min_sum比较，更新min_sum = min(min_sum, current_sum)。
这种方法的时间复杂度是 \(O(n \times m)\)。在最坏情况下，\(n=3000, m=3000\)，运算次数约为 \(3000 \times 3000 = 9 \times 10^6\)，这是可以接受的。
- 设一个变量
示例说明
输入：
8 3
1
4
7
3
1
2
4
3
n=8, m=3a = [?, 1, 4, 7, 3, 1, 2, 4, 3](数组从1开始)mi初始化为300001
i=1(子序列a[1]到a[3]):1 + 4 + 7 = 12.mi = 12.i=2(子序列a[2]到a[4]):4 + 7 + 3 = 14.mi仍是12.i=3(子序列a[3]到a[5]):7 + 3 + 1 = 11.mi = 11.i=4(子序列a[4]到a[6]):3 + 1 + 2 = 6.mi = 6.i=5(子序列a[5]到a[7]):1 + 2 + 4 = 7.mi仍是6.i=6(子序列a[6]到a[8]):2 + 4 + 3 = 9.mi仍是6.
循环结束，输出 6。
代码注释
#include<bits/stdc++.h> // 包含所有标准库，方便快速编程 (例如iostream用于输入输出，algorithm用于min函数等)
using namespace std; // 使用标准命名空间int a[3005],n,m; // 定义一个大小为3005的整型数组a，用于存储刺痛值。// 题目中n最大为3000，所以3005足够。// n和m也定义为全局变量，虽然在这里作为main函数局部变量也可以。int main()
{cin>>n>>m; // 从标准输入读取n（不爽事件总数）和m（连续事件的个数）。// 读取n个刺痛值到数组a中for(int i=1;i<=n;i++) {cin>>a[i]; // 将第i个刺痛值存储到a[i]中。}// 初始化mi为300001。// 这是为了确保任何合法的连续m个刺痛值之和都能比它小。// 因为a[i]最大100，m最大3000，所以和最大可能是 100 * 3000 = 300000。// 300001是一个安全的初始最大值。int mi=300001; // 外层循环：遍历所有可能的连续m个刺痛值序列的起始位置。// i从1开始，到 n-m+1 结束。// 例如，如果n=8, m=3，则i会从1到 8-3+1=6。// i=1: a[1],a[2],a[3]// i=2: a[2],a[3],a[4]// ...// i=6: a[6],a[7],a[8]for(int i=1;i<=n-m+1;i++) {int sum=0; // 初始化当前子序列的和为0。// 内层循环：计算当前从a[i]开始，长度为m的子序列的和。// j从i开始，到 i+m-1 结束。for(int j=i;j<=i+m-1;j++) {sum+=a[j]; // 将当前刺痛值a[j]累加到sum中。}// 比较当前子序列的和sum与目前找到的最小值mi。if(sum<mi) mi=sum; // 如果sum更小，则更新mi。// 等价于 mi = min(mi, sum); 如果使用了 <algorithm> 头文件。}cout<<mi<<endl; // 输出最终找到的最小和。return 0; // 程序正常结束。
}