P5638题解
没有传送器就好玩了......
传送器是啥？一个帮你取消掉k次走路的东西
如何使用：跳过和最大的连续k个时间
如何计算连续？前缀和！
思路：
输入完就用前缀和顶替原数组，扫一遍从哪里开始的连续k个和最大（也就是省的最多）再用原来总的（也就是此时的p[n]）减去省下的，最后输出。
而第i个到第k个省下的时间就是p[i+k]-p[i]
看代码(我这保险开了long long)
#include <bits/stdc++.h>
using namespace std;
long long n,k,p[1000001],i,j,ans;
int main(){
cin>>n>>k;
ans=2147483647214748364; //方便取小
for(i=1;i<n;i++) cin>>p[i]; //输入
for(i=2;i<n;i++) p[i]+=p[i-1]; //前缀和求取
for(i=0;i<n-k;i++) ans=min(ans,p[n-1]-p[i+k]+p[i]); //扫一遍，用从第i个开始跳算起（第i个没有被跳掉）的时间替换ans
cout<<ans； //输出
return 0;
}
}珍爱账号，请勿抄袭，抄袭有惊吓喜哦~