ZeroJudge G309: 傳遞杯子蛋糕(Cupcake)

在動物王國中，為了建立良好的傳遞網路，每個動物都會有左右需要傳東西的人，我們稱之為「左節點」和「右節點」。

其中根節點為動物王國的國王，即動物0。當動物i 拿到 K 個東西後，會將所拿到的東西以 (自己 + 子節點數量) 做均分，均分完的等份，分別傳遞給其左節點、右節點和自己做保留；若無法均分時，則會將剩下的個數優先保留給自己。

其子節點則繼續這個過程，直到沒有任何子節點為止。

ZeroJudge G309 題目解說

以上圖為例，假設動物0 拿到 9 個東西，則會其均分為三等份後，將其中 3 個傳給左邊的動物1（如紅字所示），另外 3 個傳給右邊的動物2，剩下 3 個則自己保留（螢光黃所示）。

依序同理，最後每個動物所能夠得到的物品數量如螢光黃所示。

現在已知有 N 個動物，以及動物間的左右節點關係，假設動物國的國王動物0 得到了 K 個杯子蛋糕，請問依照上述傳遞規則，每個動物最後分別可以得到幾個杯子蛋糕？

範例測資

範例輸入範例輸出
第一行有兩個正整數 N 和 K，代表總共有 N 個動物 (1 ≤ N ≤ 10)，動物編號依序為 0、1、…、N-1，並且有 K 個杯子蛋糕要由動物0 開始往下傳送。
 接著依序有 N 行，每行有三個整數 a (0 ≤ a ≤ N-1)、L 和 R (-1 ≤ L、R ≤ N-1)，代表動物a 的左子節點為 L，右子節點為 R，如果沒有該子節點，則以 -1 表示；並且動物0 必定為根節點。		由左至右，分別印出 動物0、動物1、…、動物N-1，最後可得的杯子蛋糕數量。
6 9
0 1 2
1 3 4
2 5 -1
3 -1 -1
4 -1 -1
5 -1 -1		3 1 2 1 1 1
ZeroJudge G309 範例測資

解題思路

可以宣告一個 map<int, pair<int, int>> MAP 來紀錄每一個節點的左右節點是什麼，並且宣告一個 map<int, int>ans 來存答案。

跑一個 DFS，需要的參數是目前要分的蛋糕數量 cake 和目前的節點位置 pos。預設一個變數 split 為 1，代表需要分蛋糕給多少人，如果 MAP[pos].first != -1，代表左邊有人，所以 split++，同樣如果 MAP[pos].second != -1 就代表右邊有人，所以一樣要 split++。如果 split == 1 ，代表已經不會繼續往下走了，將 ans[pos] 設為 cake 並且 return。

如果 DFS 要繼續往下走，則宣告一個變數 divide 為 cake/split，並且先將 ans[pos] 設為 divide。如果 cake % split != 0，則要將多餘的分給目前位置，所以要 ans[pos] += cake % split。

如果目前位置左邊有節點的話就呼叫 DFS，只是蛋糕數量變成 divide，並且目前位置變成 MAP[pos].first，相同道理也用在右邊。

最後跑一個 For迴圈，從 1 到 N-1，將 ans 中的資料輸出。

範例程式碼－ZeroJudge G309: 傳遞杯子蛋糕(Cupcake)

#include <iostream>
#include <map>
using namespace std;

map<int, pair<int, int>>MAP;
map<int, int>ans;

void DFS(const int cake, const int pos) {
    int split = 1;
    if (MAP[pos].first != -1) split++;
    if (MAP[pos].second != -1) split++;
    if (split == 1) {
        ans[pos] = cake;
        return;
    }
    const int divide = cake/split;
    ans[pos] = divide;
    if (cake % split != 0) ans[pos] += cake % split;
    if (MAP[pos].first != -1) DFS(divide, MAP[pos].first);
    if (MAP[pos].second != -1) DFS(divide, MAP[pos].second);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, K;
    cin >> N >> K;
    for (int i = 0; i<N; i++) {
        int a, l ,r;
        cin >> a >> l >> r;
        pair<int, int>tmp;
        tmp.first = l;
        tmp.second = r;
        MAP[a] = tmp;
    }
    DFS(K, 0);
    for (int i = 0; i<N; i++) cout << ans[i] << " ";
    cout << "\n";
}

//ZeroJudge G309
//Dr. SeanXD
標籤

相關文章

發佈留言