[数据结构与算法]P1614 爱与愁的心痛

P1614 爱与愁的心痛

题目背景

(本道题目隐藏了两首歌名，找找看哪
《爱与愁的故事第一弹 heartache》第一章。
《我为歌狂》当中伍思凯神曲《舞月光》居然没療给萨顶顶，爱与愁大神心痛啊一一而且最近还有一些令伤心的事情，都让人心痛（最近真的很烦哈

题目描述

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

输入格式

第一行有两个用空格隔开的整数，分别代表n和m
第2到第(n+1)行，每行一个整数，第(i+1)行的整数a代表第i件事的刺痛值ai.

输出格式

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

输入输出样例

输入 #1复制

8 3
1
4
7
3
1
2
4
3

输出 #1复制

6

说明/提示

数据规模与约定

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

题解

python

n,m=map(eval,input().split())
ls = [eval(input()) for i in range(n)]
res=[]
for i in range(n-m+1):
    tmp=0
    for j in range(m):
        tmp+=ls[i+j]
    res.append(tmp)
print(min(res))

c++

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,a[10010];
vector<int>v;
int main() {
    cin>>n>>m;
    for (int i = 0; i < n;cin>>a[i] ,++i);
    for (int i = 0; i < n-m+1; ++i) {
        int tmp=0;
        for (int j = 0; j < m; tmp+=a[i+j],++j);
        v.push_back(tmp);
    }
    cout<<*min_element(v.begin(),v.end());
    return 0;
}