题解 P6568 【[NOI Online #3 提高组]水壶】

· · 题解

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

因此问题就很显然地转化为了求一个长度为 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;
}