自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:22:00，当前版本为作者最后更新于2020-05-24 13:10:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

很显然每次倒水之后，水总是单调递增的，那么肯定要把这个更多的水，倒到下一个水壶里面去。也就是说每次倒水的范围是一个区间。

因此问题就很显然地转化为了求一个长度为 $k+1$ 的最大连续子段和，就可以很简单地水过去了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#include <queue>
#include <vector>

using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

int n,k,a[1000050];

long long sum,ans;

int main()
{
	freopen("kettle.in","r",stdin);
	freopen("kettle.out","w",stdout);
	n=read(),k=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	int l=1,r=k+1;
	for (int i=l;i<=r;i++)
		sum+=a[i];
	while (r<=n)
	{
		ans=max(ans,sum);
		l++;
		r++;
		sum-=a[l-1];
		sum+=a[r];
	}
	cout << ans << endl;
	return 0;
}