题解

水壶(NOI Online3 lfw数据)

题目描述

有 n 个容量无穷大的水壶，它们从 1∼n 编号，初始时 i 号水壶中装有 Ai 单位的水。
你可以进行不超过 k 次操作，每次操作需要选择一个满足 1≤x≤n−1 的编号 x，然后把 x 号水壶中的水全部倒入 x+1 号水壶中。
最后你可以任意选择恰好一个水壶，并喝掉水壶中所有的水。现在请你求出，你最多能喝到多少单位的水。

输入

第一行一个正整数 n，表示水壶的个数。
第二行一个非负整数 k，表示操作次数上限。
第三行 n 个非负整数，相邻两个数用空格隔开，表示水壶的初始装水量 A1,A2,…,An。

输出

一行，仅一个非负整数，表示答案。

样例输入

1
2
3

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

样例输出

1

3813

提示

10%的数据 n<=10
30%的数据 n<=100
50%的数据 n<=1000
70%的数据 n<=10^5
100%的数据 1<=n<=10^6, 0<=k<=n-1, 0<=Ai<=10^3

时间限制: 1.000 Sec
内存限制: 128 MB
来源：Luo’s OJ

题解

emmm……这题我们老师是用来讲对拍的
暴力也可以，但这里用的是前缀和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[1000010],sum; 
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for(int i = 1,x; i <= n; i++){
		cin >> x;
		a[i] = a[i - 1] + x;
	}
	k++;
	for(int i = 1; i + k - 1 <= n; i++) {
		int j = i + k - 1;
		sum = max(sum,a[j] - a[i - 1]);
	}
	cout << sum << endl;
	return 0;
}