当前位置: 首页 > news >正文

P1614 爱与愁的心痛

简易题解

题目大意

给定 \(n\) 个正整数,称为“刺痛值”,以及一个整数 \(m\)。我们需要找出所有连续的 \(m\) 个刺痛值之和的最小值。

思路分析

题目要求我们找到长度为 \(m\) 的连续子数组(子序列)的和的最小值。

由于 \(n\) 的最大值为 \(3 \times 10^3\),我们可以采用以下几种方法:

  1. 暴力枚举(Two Pointers / Sliding Window 简化版)
    最直观的方法是,从第一个可能的连续 \(m\) 个刺痛值序列开始,计算其和。然后依次向后移动,每次都计算一个新的连续 \(m\) 个刺痛值序列的和,并与当前记录的最小值进行比较。

    • 设一个变量 min_sum 存储目前找到的最小和,初始化为一个足够大的值(例如,所有刺痛值都取最大值100,m最大3000,则 100 * 3000 = 300000,所以300001是一个安全的初始大值)。
    • 外层循环 i\(1\) 遍历到 n - m + 1,表示连续 \(m\) 个刺痛值序列的起始位置。
    • 内层循环 ji 遍历到 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=3
  • a = [?, 1, 4, 7, 3, 1, 2, 4, 3] (数组从1开始)
  • mi 初始化为 300001
  1. i=1 (子序列 a[1]a[3]): 1 + 4 + 7 = 12. mi = 12.
  2. i=2 (子序列 a[2]a[4]): 4 + 7 + 3 = 14. mi 仍是 12.
  3. i=3 (子序列 a[3]a[5]): 7 + 3 + 1 = 11. mi = 11.
  4. i=4 (子序列 a[4]a[6]): 3 + 1 + 2 = 6. mi = 6.
  5. i=5 (子序列 a[5]a[7]): 1 + 2 + 4 = 7. mi 仍是 6.
  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; // 程序正常结束。
}
http://www.hskmm.com/?act=detail&tid=22957

相关文章:

  • P2911 [USACO08OCT] Bovine Bones G
  • STM32 智能垃圾桶项目笔记(四):PWM 回顾与舵机(SG90)控制实现 - 实践
  • 机器学习 深度学习发展简史(简化版)
  • 2025无锡黄金上门回收公司权威推荐榜:专业估价与诚信服务口碑之选
  • 详细介绍:告别“下次注意”,用这套结构化事故复盘方案就对了
  • 关于树状数组的一些东西
  • lazyVIM整体介绍、常用功能和插件
  • 【SpringAI】第四弹:深入解析 Rag 检索增强工作流程、最佳实践和调优 - 详解
  • 2025 年浮动密封厂家 TOP 企业品牌推荐排行榜,矿用,工程机械,矿山机械,煤矿井下,煤矿机械浮动密封推荐这十家公司!
  • P2141 [NOIP 2014 普及组] 珠心算测验
  • CF1081F Tricky Interactor
  • 2025.10 做题笔记
  • 2025年浮动油封厂家TOP企业品牌推荐排行榜,深度剖析技术创新与产品性能矿用,工程机械,矿山机械,煤矿井下,煤矿机械油封推荐这十家公司!
  • P1554 [USACO06DEC] 梦中的统计 Dream Counting B
  • 2025 年防火涂料厂家 TOP 企业品牌推荐红榜,膨胀型钢结构,非膨胀型钢结构,厚型钢结构,薄型钢结构,钢结构喷涂防火涂料推荐这十家优质公司!
  • 0.机器人的URDF文件修改
  • task1_1.c
  • 解码AVL树
  • LinuxWindows环境下Nacos3.1.0详细安装部署指南:从零到生产就绪
  • JAVA SE 基础语法 —— A / 初识 - 指南
  • 2025年掘进机厂家权威推荐榜:实力品牌与技术创新深度解析
  • 2025机械加工供货厂家权威口碑排行:实力与服务深度解析!
  • NOIP 集训日记 2.0
  • 2025舒适轮胎权威推荐榜:静音科技与驾乘体验口碑之选
  • 2025七水硫酸锌厂家权威推荐榜:优质供应与专业定制首选
  • 深圳网站建设公司权威推荐榜:专业定制与创新设计口碑之选
  • UV面光源实力厂家权威推荐:专业制造与品质保障口碑之选
  • 2025微弧氧化实力厂家推荐:专业表面处理技术深度解析
  • 2025减速机厂家 TOP 企业品牌推荐排行榜,谐波,行星,直角换向器,中空旋转平台,双曲面,RV,伺服,重载,步进减速机推荐这十家公司!
  • 75. 颜色分类