文章

【GESP】C++三级练习 luogu-P1614 爱与愁的心痛

发表于
作者 OneCoder
次浏览 7 分钟阅读

GESP C++三级练习，一维数组练习，难度★★☆☆☆。

luogu-P1614 爱与愁的心痛

题目要求

题目背景

（本道题目隐藏了两首歌名，找找看哪~~~）

《爱与愁的故事第一弹·heartache》第一章。

《我为歌狂》当中伍思凯神曲《舞月光》居然没赢给萨顶顶，爱与愁大神心痛啊~~~而且最近还有一些令人伤心的事情，都让人心痛（最近真的很烦哈)……

题目描述

最近有 $n$ 个不爽的事，每句话都有一个正整数刺痛值（心理承受力极差）。爱与愁大神想知道连续 $m$ 个刺痛值的和的最小值是多少，但是由于业务繁忙，爱与愁大神只好请你编个程序告诉他。

输入格式

第一行有两个用空格隔开的整数，分别代表 $n$ 和 $m$。

第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数 $a_i$ 代表>第 $i$ 件事的刺痛值 $a_i$。

输出格式

输出一行一个整数，表示连续 $m$ 个刺痛值的和的最小值是多少。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9

8 3
1
4
7
3
1
2
4
3

输出 #1

1
2

6

数据规模与约定

  • 对于 $30\%$ 的数据，保证 $n \leq 20$。
  • 对于 $60\%$ 的数据，保证 $n \leq 100$。
  • 对于 $90\%$ 的数据，保证 $n \leq 10^3$。
  • 对于 $100\%$ 的数据，保证 $0 \leq m \leq n \leq 3 \times 10^3$，$1 \leq a_i \leq 100$。

题目分析

解题思路

本题的解题思路如下：

  1. 问题本质：
    • 在给定的n个数字中，找出连续m个数字之和的最小值
    • 需要考虑所有可能的连续m个数字组合
    • 最终输出这些组合中的最小和
  2. 解题关键：
    • 有两种主要解题方法：双层循环和滑动窗口
    • 双层循环：遍历所有可能的连续m个数字组合
    • 滑动窗口：维护一个大小为m的窗口，逐个向右滑动
  3. 实现思路：
    • 方法一（双层循环）：
      • 外层循环遍历起始位置（0到n-m）
      • 内层循环计算从起始位置开始的m个数字之和
      • 记录并更新最小和
    • 方法二（滑动窗口）：
      • 先计算前m个数字的和
      • 然后每次减去窗口最左边的数，加上新的数
      • 动态更新最小和
  4. 复杂度分析：
    • 双层循环方法：时间复杂度 $O(n×m)$，空间复杂度 $O(1)$
    • 滑动窗口方法：时间复杂度 $O(n)$，空间复杂度 $O(1)$

示例代码

方法一：双层循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <iostream>
#include <cmath>

// 定义数组存储每个事件的刺痛值
int array[3005];
int main() {
    // 定义变量n表示事件总数，m表示连续事件数
    int n, m;
    // 从标准输入读取n和m
    std::cin >> n >> m;
    // 读取每个事件的刺痛值
    for (int i = 0; i < n; i++) {
        std::cin >> array[i];
    }
    // 初始化最小和为一个较大的值
    int min_sum = 30000000;
    // 遍历所有可能的连续m个事件的组合
    for (int i = 0; i <= n - m; i++) {
        // 计算当前连续m个事件的刺痛值之和
        int cur_sum = 0;
        for (int j = i; j < i + m; j++) {
            cur_sum += array[j];
        }
        // 更新最小和
        min_sum = std::min(min_sum,cur_sum);
    }
    // 输出连续m个刺痛值的最小和
    std::cout << min_sum;
    return 0;
}

方法二：单层循环，滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <cmath>
#include <iostream>


// 定义数组存储刺痛值，大小为3005以满足数据范围要求
int array[3005];
int main() {
    // 定义n表示事件总数，m表示连续事件数
    int n, m;
    std::cin >> n >> m;

    // m_sum用于存储当前窗口的和，min_sum存储最小和
    int m_sum = 0;
    int min_sum = 0;
    // 遍历所有事件
    for (int i = 1; i <= n; i++) {
        // 读取每个事件的刺痛值
        std::cin >> array[i];
        if (i <= m) {
            // 前m个数直接累加
            m_sum += array[i];
            min_sum = m_sum;
        } else {
            // 滑动窗口：减去窗口最左边的值，加上新的值
            m_sum = m_sum - array[i - m] + array[i];
            // 更新最小和
            min_sum = std::min(min_sum, m_sum);
        }
    }
    // 输出连续m个刺痛值的最小和
    std::cout << min_sum;
    return 0;
}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页

“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限，欢迎加入。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。

GESP, 三级
GESP C++
本文由作者按照 CC BY 4.0 进行授权