分蛋糕

形式化题目

有 $n$ 块重量分别为 $a_1, a_2, \ldots, a_n$ 的蛋糕，按编号从小到大依次分配给排队的若干朋友。每个朋友从当前最小编号的蛋糕开始领取，直到其总重量不小于 $k$ 或蛋糕分完为止。求最终拿到蛋糕的朋友数量。

思路

蛋糕的领取顺序完全由编号决定，朋友们只是被切分成连续的若干段，因此可以一趟扫描完成。

分组规则

把蛋糕序列切成尽量多的连续段，每段的总重量不小于 $k$ ；最后一段即使不足 $k$ 也仍然由一位朋友拿走。分到的朋友数就是段数。

扫描累计

先看一个按题意逐朋友模拟的朴素写法：

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:48
 */
// brute.cpp：按题意逐个朋友、逐块蛋糕模拟分配过程。
#include <bits/stdc++.h>
using namespace std;

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

    int n, k;
    cin >> n >> k;
    vector<int> cake(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> cake[i];
    }

    int position = 1;
    int answer = 0;
    while (position <= n) {
        int current_weight = 0;
        answer++;
        while (position <= n && current_weight < k) {
            current_weight += cake[position];
            position++;
        }
    }
    cout << answer << '\n';

    return 0;
}

正式实现不需要保存每一组。扫描每块蛋糕时维护当前朋友已拿到的重量 current_weight：

加入本块后若重量达到 $k$ ，这位朋友结束，答案加一并把累计重量清零；
若加入后仍不足 $k$ ，继续为下一位朋友累计。

扫描结束后，若累计重量非零，说明还有一位朋友拿走了不足 $k$ 的剩余蛋糕，答案再加一。

代码

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/**
 * 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-31 16:21
 * update_at: 2026-08-17 22:48
 */
#include <bits/stdc++.h>
using namespace std;

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

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

    int current_weight = 0; // 当前这位朋友已拿到的总重量
    int answer = 0;
    for (int i = 1; i <= n; i++) {
        int cake_weight;
        cin >> cake_weight;
        current_weight += cake_weight;
        // 累计达到 k 后结束当前朋友，从下一位朋友重新开始累计
        if (current_weight >= k) {
            answer++;
            current_weight = 0;
        }
    }
    // 蛋糕全部分完时，最后一位朋友即使拿到的重量不足 k，也带走了剩余蛋糕
    if (current_weight > 0) {
        answer++;
    }
    cout << answer << '\n';

    return 0;
}

复杂度

时间：每块蛋糕只被处理一次，时间复杂度为 $O(n)$ 。
空间：只维护一个累计变量，额外空间复杂度为 $O(1)$ 。

总结

分组边界恰好是前缀和第一次达到 $k$ 的位置。最后一组不必达到 $k$ ，只要还有蛋糕就必须计入答案，这是最容易漏掉的边界情况。

目录

形式化题目

思路

分组规则

扫描累计

代码

复杂度

总结