[NOI Online #3 提高组] 水壶

题意

有 n 个水壶，初始第 i 个水壶里有 $A_i$ 单位的水。
一次操作可以把第 x 个水壶里的水全部倒进第 x+1 个水壶里，最多做 k 次。
最后只能选择恰好一个水壶喝掉，问最多能喝到多少水。

关键限制是：水只能往右倒，而且一次操作只跨一条相邻边。
所以如果最后选择喝第 r 个水壶，那么能并进来的只可能是它左边一段连续水壶。

思路

先看一个最直接的朴素枚举：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<ll> a(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    ll ans = 0;
    for (int right = 1; right <= n; ++right) {
        ll sum = 0;
        for (int left = right; left >= 1 && right - left <= k; --left) {
            sum += a[left];
            ans = max(ans, sum);
        }
    }

    cout << ans << '\n';
    return 0;
}

如果最后喝的是第 r 个水壶，想把第 l..r 这些水都并到 r，需要做 r-l 次操作：
l -> l+1 -> ... -> r。
因此只要满足 $r-l \leqslant k$ ，区间 $[l,r]$ 就是可行的。

于是题目等价于：

在数组 A 中找一个连续区间；
区间长度不超过 k+1；
使区间和最大。

朴素做法就是枚举右端点 r，再枚举能选到的左端点 l，统计所有合法区间和。
这正是 brute.cpp 的做法，复杂度是 $O(nk)$ ，显然扛不住 n=10^6。

接下来只差一个观察：题目保证 $A_i \geqslant 0$ 。
既然每个水壶里的水都不会是负数，那么右端点固定时，区间越长，和只会越大，不会变小。
所以对固定的 r，最优左端点一定是能取得最靠左那个，也就是：

$l = \max(1, r-k)$ 。

这样答案就变成了：

$\max(sum(\max(1,r-k) \dots r))$

也就是每个右端点只看一个区间。
用前缀和就能在 $O(1)$ 时间求这个区间和，总复杂度降成 $O(n)$ 。

区间是怎么来的

这张表展示固定右端点后，可行区间为什么一定是连续的一段。

最终喝的水壶	最多操作数	最左能并到哪里	对应区间
`r`	`k`	`r-k`	`[r-k, r]`
`r` 在前面不足 `k` 个位置	`k`	`1`	`[1, r]`

因为每次只能把 x 倒进 x+1，所以想把更左边的水送到 r，中间每个水壶都必须依次经过。
这意味着可并进来的部分不可能跳着选，只能是一段连续区间。
又因为每经过一条边就花一次操作，所以最多只能覆盖 k+1 个连续水壶。

实现上直接套前缀和模板即可，这部分思路和 rbook 的文章前缀和一致。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct PrefixSum {
    vector<ll> s;

    void init(const vector<ll> &a) {
        int n = static_cast<int>(a.size());
        s.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            s[i] = s[i - 1] + a[i - 1];
        }
    }

    ll query(int l, int r) const {
        return s[r] - s[l - 1];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    PrefixSum ps;
    ps.init(a);

    ll ans = 0;
    for (int right = 1; right <= n; ++right) {
        // 右端点固定为 right 时，最多再向左并进来 k 个水壶。
        int left = max(1, right - k);
        ans = max(ans, ps.query(left, right));
    }

    cout << ans << '\n';
    return 0;
}

复杂度

设数组长度为 n。
预处理前缀和是 $O(n)$ 。
枚举每个右端点并计算对应区间和也是 $O(n)$ 。
总时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

这题表面是倒水操作，实质是连续区间最大和，只不过区间长度被限制为不超过 k+1。
真正决定能否化简的是两个条件：

水只能向右流，所以选中的水壶必须连续。
$A_i$ 全都非负，所以固定右端点时，直接取能覆盖到的最长区间就是最优。

把这两个条件看清楚，题目就自然落到前缀和上了。

[NOI Online #3 提高组] 水壶

目录

题意

思路

区间是怎么来的

代码

复杂度

总结