洛谷:P1614:爱与愁的心痛


洛谷:P1614:爱与愁的心痛

Table of Contents

题目

P1614:爱与愁的心痛

分析

洛谷的书上,强烈提示:仅使用一重循环完成此题。这就要求我们别用常规的双重循环方式——第一重切换区间,第二重计算区间和——而是换一种方式。

在区间长度m确定的情况下,我们只要用一次循环就可以找出所有长度为m的区间。而且可以观察到:每次窗口右移一格,就有一个数字退出、一个数字进入。所以,在求这个区间内的数字和时,不必再用循环求和,而是可以直接用之前的和减去一个再加上一个的方法。我们只要确定退出的数字的位置(i-m)和进入的数字的位置(i)即可。

    for(int i=m;i<n-1;i++)
    {
        tmp=tmp-sadness[i-m]+sadness[i];
        if(tmp<min_sadness)
        {
            min_sadness=tmp;
        }
    }

这样我们只需要用一个循环!

注意:这么做的时候,需要先算第一个起始区间的数字和。

答案

思考

这题用到了一个“滑动窗口”的概念,是值得注意的。

Previous Next