ZeroJudge 解題筆記：g309. pC. 傳遞杯子蛋糕(Cupcake)

作者：王一哲
日期：2025年11月4日


ZeroJudge 題目連結：g309. pC. 傳遞杯子蛋糕(Cupcake)

解題想法

先讀取節點之間的關係，如果是 -1 代表沒有這個子節點。用串列 cnt 儲存每個節點分配到的數量，根節點先分到全部的數量 k。接下來用 BFS 走訪每個節點，計算要平分的數量 m 及平均值 avg。

Python 程式碼

使用時間約為 22 ms，記憶體約為 3.7 MB，通過測試。

from collections import deque

n, k = map(int, input().split())  # n 個節點，有 k 個東西要分配
tree = [[0, 0] for _ in range(n)]  # 節點的關係，i: [left, right]
for _ in range(n):  # 讀取 n 行資料
    i, left, right = map(int, input().split())
    tree[i] = [left, right]
cnt = [0]*(n)  # 各節點分配到的數量
cnt[0] = k  # 根節點先分到全部的數量
que = deque([0])  # 待走訪節點，先放入 0
while que:  # 若 que 還有資料繼續執行
    u = que.popleft()  # 從 que 開頭取出待走訪節點 u
    left, right = tree[u]  # u 的左節點、右節點
    m = 1 + (left != -1) + (right != -1)  # 共有 m 個點要平分數量，至少有 1 個點
    tot = cnt[u]  # 目前 u 節點擁有的數量
    avg = tot//m  # tot 除以 m 的平均值
    cnt[u] = avg + tot%m  # u 的數量改成 avg 加上 tot 除以 m 的餘數
    if left != -1:  # 如果有左子節點
        cnt[left] = avg; que.append(left)  # left 分到的數量為 avg，left 加入 que
    if right != -1:
        cnt[right] = avg; que.append(right)  # right 分到的數量為 avg，right 加入 que
print(*cnt)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 280 kB，通過測試。

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

int main() {
    int n, k; scanf("%d %d", &n, &k);  // n 個節點，有 k 個東西要分配
    int tree[n][2];  // 節點的關係，i: [left, right]
    memset(tree, 0, sizeof(tree));
    for(int j=0; j<n; j++) {  // 讀取 n 行資料
        int i, left, right; scanf("%d %d %d", &i, &left, &right);
        tree[i][0] = left; tree[i][1] = right;
    }
    int cnt[n] = {0};  // 各節點分配到的數量
    cnt[0] = k;  // 根節點先分到全部的數量
    queue<int> que; que.push(0);  // 待走訪節點，先放入 0
    while(!que.empty()) {  // 若 que 還有資料繼續執行
        int u = que.front(); que.pop();  // 從 que 開頭取出待走訪節點 u
        int left = tree[u][0], right = tree[u][1];  // u 的左節點、右節點
        int m = 1 + (left != -1) + (right != -1);  // 共有 m 個點要平分數量，至少有 1 個點
        int tot = cnt[u];  // 目前 u 節點擁有的數量
        int avg = tot/m;  // tot 除以 m 的平均值
        cnt[u] = avg + tot%m;  // u 的數量改成 avg 加上 tot 除以 m 的餘數
        if (left != -1) {  // 如果有左子節點
            cnt[left] = avg; que.push(left);  // left 分到的數量為 avg，left 加入 que
        }
        if (right != -1) {
            cnt[right] = avg; que.push(right);  // right 分到的數量為 avg，right 加入 que
        }
    }
    for(int i=0; i<n-1; i++) printf("%d ", cnt[i]);
    printf("%d\n", cnt[n-1]);
    return 0;
}