可以用简单的数论,o(n)的复杂度。
就拿样例1说,你要求4,8,16的和就要把所有数的和减去1,2的和,可以的到公式ans=sum[i]-sum[i-k]。
sum[i]是前i项的和 , sum[i-k]是前i-k项的和 ,前提是要i-k大于等于0,最后把ans加起来就可以了
代码如下:
#include<iostream>//头文件
using namespace std;
const int N=1e5+1;
long long sum[N];
int main()
{
int n,k;
cin>>n>>k;
long long ans=0;
for(int i=1;i<=n;++i)
{
int c=0;
cin>>c;
sum[i]=sum[i-1]+c;
if(i-k>=0)
ans+=sum[i]-sum[i-k];//利用公式得出答案
}
cout<<ans;
return 0;
}
Comments | NOTHING