前缀和。
#重点在一个小小的常数优化
但是数据大了以后比楼下们跑的会快!!!
楼下用前缀和的题解都是跑了两遍循环。
而实际上一遍循环就可以呀。
就是加一段这个
if(i>=m) if(low>(ans[i]-ans[i-m])) low=ans[i]-ans[i-m];
直接维护一个low值就好。每次输入都判一下就简单很多。
直接上完整代码。
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std;///头文件们不说 int n,m; long long ans[3005];//用于储存前缀和的数组 int num[3005];//储存数据 long long low=0x3f3f3f3f;//要维护的对象。最小值 int main() { cin>>n>>m;//输入 for(int i=1;i<=n;i++) { cin>>num[i];//输入 ans[i]=ans[i-1]+num[i];//计算前缀和 if(i>=m)//好了亮点在这!!!不用再扫一遍。//就是可以截取以这个点为重终点的区间时 { if(low>(ans[i]-ans[i-m]))//如果以前的最小值小于这一段的最小值。 { low=ans[i]-ans[i-m];//更新 } } } if(low==0x3f3f3f3f)//如果发现没有更新 { printf("0");//那就是0; return 0; } printf("%lld",low);//直接输出 return 0;//程序拜拜
不过用scanf还会快一点