题解 | 空间跃迁

#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using u128=__uint128_t;
using ld=long double;

void solve()
{//据题意 我们使用传送后 可以节省包括本身i在内 从a[i]到a[i+k-1]的所有时间
//所以我们找出最大的一段a[i]到a[i+k-1]即可 我们可以构建前缀和数组 使计算这段时间时时间复杂度为O（1）
//遍历数组计算每个元素往后的一段 比较找出最大值 然后与总时间相减即可 总体时间复杂度为O（n）
    ll n,k,sum=0,MAX=0;
    cin >> n >> k;
    vector<ll>a(n+1,0),pre(n+1,0);
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        pre[i]=pre[i-1]+a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n-k;i++)
    {
        MAX=max(MAX,pre[i+k-1]-pre[i]+a[i]);
    }
    cout << sum-MAX;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t=1;
	//cin >> t;
	
	while(t--)
	{
		solve();
	}
	return 0;
}