什么是前缀和和前缀积？ 前缀和、前缀积也称前缀和数组，前缀积数组。 给一数组A， 前缀和：新建一数组B，数组中每一项B[i]保存A中[0…i]的和； 后缀和：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的和； 前缀积：新建一数组B，数组中每一项B[i]保存A中[0…i]的积； 后缀积：新建一数组B，数组中每一项B[i]保存A中[i…n-1]的积；
题目描述： 输入n个数的数列，所有相邻m数的和有n-m+1个，求其中的最小值。 输入格式： 第一行，n,m 第二行，有n个正整数 输出格式： 输出最小值 输入样例： 6 3 10 4 1 5 5 2 输出样例： 10这就是一道典型的通俗易懂的简单的前缀和求最小值的问题 首先我拿到题面，不看题解，直接硬刚（注意，这里的代码运用了多层嵌套并没有使用前缀和算法，所以会比较冗杂，但是作为新手学思路也不失为一种可行的方法）
#include<iostream> #include<string.h> using namespace std; int main() { long long n,m,final; int a[20],sum[10]; memset(sum,0,sizeof(sum)); while(cin>>n>>m) { for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int q=1;q<=m;q++) { sum[1]+=a[q]; } final=sum[1]; for(int i=2;i<=n-m+1;i++) { for(int j=i;j<i+m;j++) { sum[i]+=a[j]; } final=(sum[i-1]>=sum[i])?final=sum[i]:final=final; } cout<<final<<endl<<endl; } return 0; }接下来我将会利用“前缀和算法”来进行运算：
#include<bits/stdc++.h> using namespace std; const int INF=0x3f3f3f; int main() { int a[1000]={0}, sum[1000]; int n, m; cin>>n>>m; for(int i=1; i<=n; i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i];//依次求i之前的数组的和 } int min=INF; for(int i=0; i<=n-m; i++) { min=min<(sum[i+m]-sum[i])?min:(sum[i+m]-sum[i]);//通过比较取最小的组 } cout<<min<<endl; return 0; }