爱那句话歌 https://blog.csdn.net/m0_74031997/article/details/143729131

爱那句话歌 https://blog.csdn.net/m0_74031997/article/details/143729131

个人问题清单

团队问题清单

节省

问题提供者是孤独感

遇到困难

历史分数100

提交记录以查看问题

标签

Luogu原创

查看算法标签

输入讨论版本

相关讨论

查看讨论

推荐主题

查看建议

复制并扩展

问题背景

（这个标题隐藏了两个歌曲，找出在哪里阅读~~~）

“爱与悲伤的故事”的第1章

在《我是疯狂的歌》中，吴西凯的神圣歌曲“舞月”并没有被sa丁丁赢得。爱与悲伤之神是伤心欲绝的~~~，最近有一些可悲的事情令人心碎（我最近真的很烦人）。

问题描述

最近，我有一件坏事，每个句子都有积极的整数刺痛价值（非常差的心理耐力）。伟大的大师爱与悲伤想知道连续的MM刺痛价值的最低价值，但是由于繁忙的业务，伟大的大师的爱和悲伤不得不要求您编写一个程序来告诉他。

输入格式

第一行的两个整数分别由空间隔开，分别代表NN和MM。

从第22行到（n+1）（n+1），每条线都有一个整数，并且在行（i+1）（i+1）（i+1）（i+1）中的整数AIAI表示IITH事物的刺激值AIAI。

输出格式

在连续输出整数，指示连续MM STING值之和的最小值是多少。

输入和输出示例

输入＃1复制

8 3
1
4
7
3
1
2
4
3

输出＃1副本

6

描述/提示数据大小和协议

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Practise___11._12_Love_and_Heart___number2
{
    internal class Program
    {
        static void Main(string[] args)
        {
            LoveHeart(); // 调用 LoveHeart 方法
            Console.ReadKey(); // 等待用户按下任意键
        }
        static void LoveHeart()
        {
            string[] firstline = Console.ReadLine().Split(' '); // 从控制台读取一行输入并按空格分割成字符串数组
            int n = int.Parse(firstline[0]); // 将第一个字符串转换为整数 n
            int m = int.Parse(firstline[1]); // 将第二个字符串转换为整数 m
            int[] a = new int[n]; // 创建一个长度为 n 的整数数组 a
            for (int i = 0; i < n; i++)
            {
                a[i] = int.Parse(Console.ReadLine()); // 从控制台读取 n 个整数并存入数组 a
            }
            int minSum = int.MinValue; // 初始化最小和为一个很大的数（实际上应该是 int.MaxValue）
            int currentSum = 0; // 用于计算当前窗口的和
            for (int i = 0; i < m; i++)
            {
                currentSum += a[i]; // 计算第一个窗口的和
            }
            minSum = currentSum; // 将第一个窗口的和赋值给 minSum
            // 使用滑动窗口计算后续的和
            for (int i = m; i < n; i++)
            {
                currentSum += a[i] - a[i - m]; // 更新当前窗口的和
                if (currentSum < minSum) // 如果当前窗口的和小于 minSum
                {
                    minSum = currentSum; // 更新 minSum
                }
            }
            Console.WriteLine(minSum); // 输出最小和
        }
    }
}

解释：

初始化窗口：首先，代码计算数组A中的第一个M元素的总和，该总和称为当前窗口的总和（）。该窗口的大小为m。

更新最小值：将当前窗口的总和与已知最小总和（）进行比较，然后更新最低总和。

滑动窗口：接下来，代码通过移动窗口来计算后续总和。具体而言，当窗口向右滑动时：

继续更新最小总和：每次滑动窗口后，检查当前窗口的总和小于已知的最低总和并进行更新。

这样，代码可以在O（n）的时间复杂性内找到长度M的最小总和，而无需使用嵌套环来计算每个子阵列的总和，这更有效。

总而言之，滑动窗口是一种有效的算法设计模式，适合处理连续的子阵列问题，并且可以显着降低计算的复杂性。