爱与愁的心痛
求连续 m 个刺痛值之和的最小值
正文
// 原题：https://oj.yecheng.tv/p/1405
// 题意：n 个刺痛值，求连续 m 个的和的最小值。
// 思路：滑动窗口，维护当前窗口和，逐位右移并更新最小和。
// 复杂度：O(n)。
// 易错点：窗口长度恰为 m；初值取第一个窗口的和。
#include <iostream>
using namespace std;
int main(){
int n, m, a[3005], sum = 0, mn = 2000000000;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < m; i++) sum += a[i];
mn = sum;
for(int i = m; i < n; i++){
sum = sum - a[i - m] + a[i];
if(sum < mn) mn = sum;
}
cout << mn << endl;
return 0;
}
洛谷·深入浅出的其它内容
- 简单的分苹果
- 简单的分苹果 2
- 圆的计算
- 简单的猴子吃桃
- 评测机队列
- 面积计算
- 竞赛得分
- 简单的分苹果 3
- 鸡兔共笼
- 定期存款
- 跑步
- 英文字母
- 玩橡皮泥
- 销量预测
- 苹果采购
- 字母转换
- 数字反转
- 再分肥宅水
- 小鱼的游泳时间
- 成绩
- 上学迟到
- 三角形面积
- 小玉买文具
- 苹果和虫子
- 对角线
- 数字比较
- 数的性质
- 闰年判断
- Apples
- 洛谷团队系统
- 肥胖问题
- 三位数排序
- 月份天数
- 不高兴的津津
- 买铅笔
- 三角形分类
- 小玉家的电费
- 小鱼的航程（改进版）
- 三角函数
- 陶陶摘苹果
- [COCI2006-2007#2] ABC
- 找最小值
- 分类平均
- 一尺之棰
- 数字直角三角形
- 阶乘之和
- 计数问题
- 级数求和
- 金币
- 数列求和
- 质数口袋
- 回文质数 Prime Palindromes
- 小玉在游泳
- 数字反转
- 月落乌啼算钱（斐波那契数列）
- 求极差 / 最大跨度值
- 最长连号
- 质因数分解
- 求三角形
- 打分