题解 P1614 【爱与愁的心痛】

· · 题解 

#include <stdio.h>
int val[3001],n,m,ans;
int main() {
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i) 
        scanf("%d",&val[i]),ans+=val[i];//先输入前m个,并求和 
    int minn=ans;
    for(int i=m+1;i<=n;++i) {//从第m+1个开始，比较 n-m次求最小值 
        scanf("%d",&val[i]);
        ans=ans-val[i-m]+val[i];//区间整体向后移动一次，即移出val[i-m]，加入val[i] 
        minn=minn>ans?ans:minn;//==> minn=min(minn,ans);
    }
    printf("%d",minn);
    return 0;
}

举个栗子：

8 3

1 4 7 3 1 2 4 3

前三个和为：1+4+7=12，此时m个为 1 4 7

1、移出1，加入3，此时m个为4 7 3 ，和为：4+7+3=14，所以此时最小值为12

2、移出4，加入1，此时m个为7 3 1 ，和为：7+3+1=11，所以此时最小值为11

3、移出4，加入1，此时m个为3 1 2 ，和为：3+1+2=6 ，所以此时最小值为6

......

循环n-m次后，就能找到最小值