题目描述

有 n 个容量无穷大的水壶，它们从 1∼n 编号，初始时 i 号水壶中装有 Ai

单位的水。

你可以进行不超过 k
次操作，每次操作需要选择一个满足 1≤x≤n−1 的编号 x，然后把 x 号水壶中的水全部倒入 x+1

号水壶中。

最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

样例

输入样例：

10
5
890 965 256 419 296 987 45 676 976 742

输出样例：

3813

(贪心)

_**这道题目，是用贪心算法的，由于要得到最多的水，就有一个显然的策略，就是用k次把p-k,p-k+1,......,p-1这
些水壶中的水，按照从左到右，都放入第p个水壶中。**_

时间复杂度 $O(n)$

为了让代码更优化一些，我们可以直接一边输入一边计算。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c[1000000];     //a表示水壶数量，b表示操作次数，c数组表示各个水壶里面装水的多少
long long s=0;          //最终答案
int main()
{
    cin>>a>>b;

    if(a<=b)  //特殊情况，直接把所有的加起来
    {
        for(int i=0;i<a;i++)
        {
            int h;
            cin>>h;
            s+=h;
        }
    }
    else
    {
        long long now=0;
        for(int i=0;i<a;i++)
        {
            cin>>c[i];
            if(i<b)             //先装满初始时候的水
            {
            now+=c[i];
            }
            else
            {
            now+=c[i]-c[i-b-1];//调换
            s=max(now,s);
            }
        }
    }

    cout<<s<<endl;
    return 0;
}