题目
分析
洛谷的书上,强烈提示:仅使用一重循环完成此题。这就要求我们别用常规的双重循环方式——第一重切换区间,第二重计算区间和——而是换一种方式。
在区间长度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;
}
}
这样我们只需要用一个循环!
注意:这么做的时候,需要先算第一个起始区间的数字和。
答案

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