P6568 [NOI Online #3 提高组] 水壶

一、题目描述

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

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

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

二、解题思路

核心观察

每次操作只能将 x 号水壶的水倒入 x+1 号，这意味着水只能向右合并，无法向左移动。因此，最终水量最多的水壶必然是通过合并其左侧连续若干个水壶的水得到的。

例如：若最终选择第 i 个水壶，则它的水量可能是 $A [i]（未合并）、A [i-1]+A [i]$（合并 1 次）、$A [i-2]+A [i-1]+A [i]$（合并 2 次）等，最多可合并左侧 i-1 个水壶（需 i-1 次操作）。

具体策略

1、前缀和预处理：计算前缀和数组 S，其中 S [i] 表示前 i 个水壶的总水量$（S [0]=0，S [i]=A [1]+A [2]+…+A [i]）$这样，区间 $[l, r]$ 的总水量可表示为 $S [r]-S [l-1]$。

2、滑动窗口枚举：对于每个右侧端点 r（即最终选择的水壶），寻找最大的 $l（l≤r）$，使得合并次数$（r-l）≤k$此时，区间$ [l, r]$ 的总水量 $S [r]-S [l-1]$ 就是该水壶可能的最大水量。

3、取最大值：遍历所有可能的 r，计算对应的最大水量，取其中的最大值即为答案。

三、代码实现

#include<bits/stdc++.h>
using namespace std;
int a[1000009],sum[1000009];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	int maxx=-1;                             
	for(int i=k+1;i<=n;i++){
		int t=sum[i]-sum[i-k-1];
		maxx=max(maxx,t);
	}
	cout<<maxx;
	return 0;
}

四、总结

该题通过简单的前缀和与枚举策略，高效解决了有限次操作下的最大化问题，体现了将实际操作转化为数学模型的解题思路。