[USACO23DEC] Candy Cane Feast B

同题版本

本题对应的 USACO 版本及解析：

usaco-1347 Candy Cane Feast

题意

有 n 头奶牛和 m 根糖果棒。

每根糖果棒都按输入顺序依次喂，奶牛也总是按 1..n 的顺序去吃。

对一根高度为 x 的糖果棒：

初始时它占据区间 [0, x]；
如果前面的奶牛已经把底部吃到了高度 taken；
那么当前这头奶牛最多只能再吃到 min(h[i], x)。

所以她这次真正吃到的长度就是：

max(0, min(h[i], x) - taken)

吃完后，这部分长度会加到她的身高上，再处理下一头奶牛。所有糖果棒处理完后，输出每头奶牛的最终身高。

思路

最直接的做法就是严格按题意模拟。

对每根糖果棒维护一个 taken，表示这根糖果棒底部已经被吃到了多高，然后让每头奶牛依次尝试去吃。

这个版本最容易理解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n, m;
long long h[MAXN];
long long candy[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> candy[i];
    }

    // 朴素模拟：每根糖果棒都让所有奶牛按顺序尝试一次。
    for (int i = 1; i <= m; i++) {
        long long taken = 0;
        for (int j = 1; j <= n; j++) {
            long long reach = min(h[j], candy[i]);
            if (reach > taken) {
                h[j] += reach - taken;
                taken = reach;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << h[i] << '\n';
    }
    return 0;
}

但如果每根糖果棒都把所有奶牛扫一遍，复杂度会到 $O(nm)$ 。

关键观察在第一头奶牛身上。

为什么整行扫描不会发生很多次

只有当糖果棒高度 x 严格大于第一头奶牛当前身高 h[1] 时，第一头奶牛才无法独自吃完整根糖果棒，后面的奶牛才会有机会参与。

而一旦这件事发生，第一头奶牛本轮一定会吃掉从 0 到 h[1] 的整段，所以她本轮恰好增加 h[1] 的高度，也就是：

h[1] <- 2 * h[1]

也就是说：

只要某一轮需要继续往后扫很多头奶牛；
那么这一轮结束后，第一头奶牛至少翻倍一次。

由于每根糖果棒高度都不超过 $10^9$ ，第一头奶牛最多翻倍大约 30 次，就一定已经不小于所有糖果棒高度。

从那以后，每一根糖果棒都会被第一头奶牛直接吃完，这一轮只需要 $O(1)$ 。

正式做法

对每根糖果棒 x：

如果 x <= h[1]，直接令 h[1] += x；
否则顺着题意模拟，并维护 taken；
一旦 $taken == x$ ，说明糖果棒已经吃完，立刻结束这一轮。

这样总复杂度就是 $O(m + n log 10^9)$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;

int n, m;
long long h[MAXN];

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    for (int i = 1; i <= m; i++) {
        long long x;
        cin >> x;

        // 如果第一头牛已经能吃完整根糖果棒，后面的牛不可能再吃到。
        if (x <= h[1]) {
            h[1] += x;
            continue;
        }

        long long taken = 0; // 当前已经被吃到的最高位置
        for (int j = 1; j <= n && taken < x; j++) {
            long long reach = min(h[j], x);
            if (reach > taken) {
                h[j] += reach - taken;
                taken = reach;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << h[i] << '\n';
    }
    return 0;
}

复杂度

时间复杂度： $O(m + n log 10^9)$
空间复杂度： $O(n)$

总结

这题的代码本身并不复杂，真正难点在复杂度证明。

抓住“只要后面的奶牛能吃到，第一头奶牛就会翻倍”这一点，就能知道真正昂贵的整行扫描只会发生很少几次。