Candy Cane Feast

题意

有 $N$ 头牛，每头牛有一个当前身高。

FJ 依次把 $M$ 根糖棒竖直挂起来，从地面开始。每根糖棒都会让牛按编号顺序尝试吃。

一头牛最多只能吃到自己当前身高能触及的位置；吃掉多少糖棒，她的身高就增加多少。

求所有糖棒喂完后每头牛的最终身高。

思路

暴力想法

按题意模拟即可。

对当前糖棒维护一个变量 eaten，表示从地面到高度 eaten 的部分已经被吃掉了。

一头牛高度为 h：

如果 $h <= eaten$ ，她吃不到；
如果 h > eaten，她能吃掉从 eaten 到 min(h,candy) 的部分。

这个直接模拟版本适合理解题意：

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
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:56
 * update_at: 2026-07-11 12:57
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

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

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

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

    for (int j = 1; j <= m; j++) {
        long long candy;
        cin >> candy;
        long long eaten = 0;

        // 暴力直接让每头牛都尝试一次，不提前跳出。
        for (int i = 1; i <= n; i++) {
            if (height_cow[i] > eaten) {
                long long top = min(height_cow[i], candy);
                long long add = top - eaten;
                height_cow[i] += add;
                eaten = top;
            }
        }
    }

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

    return 0;
}

提前停止

如果 $eaten == candy$ ，说明当前糖棒已经完全被吃完，后面的牛不可能再吃到。

所以正解只需要在当前糖棒吃完时退出这一轮，进入下一根糖棒。

更新过程是：

text

1
2
3
4top = min(height_cow[i], candy)
add = top - eaten
height_cow[i] += add
eaten = top

这里 add 就是第 i 头牛实际吃掉的长度。

代码

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 12:56
 * update_at: 2026-07-11 12:57
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

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

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

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

    for (int j = 1; j <= m; j++) {
        long long candy;
        cin >> candy;

        long long eaten = 0; // 当前糖棒 [0,eaten] 这一段已经被吃掉。
        for (int i = 1; i <= n && eaten < candy; i++) {
            if (height_cow[i] > eaten) {
                long long top = min(height_cow[i], candy);
                long long add = top - eaten;
                height_cow[i] += add;
                eaten = top;
            }
        }
    }

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

    return 0;
}

复杂度

使用一个变量维护当前糖棒状态，空间复杂度 $O(N)$ 。

官方解析说明，在糖棒吃完后提前停止的模拟可以通过本题数据范围。注意所有高度和增长量都要使用 long long。

总结

这题的关键是把糖棒剩余状态压缩成一个高度 eaten。

每头牛只会影响从 eaten 到自己能触及高度之间的区间，更新这个高度后继续模拟即可。

目录

题意

思路

暴力想法

提前停止

代码

复杂度

总结