g309 - pC. 傳遞杯子蛋糕(Cupcake)
題目描述
題目描述了一個杯子蛋糕傳遞的過程，其中一個動物可以將其擁有的杯子蛋糕均分給其左右子節點，並保留剩餘的杯子蛋糕。目標是計算每個動物最終可以獲得多少杯子蛋糕。
解題思路
這題可以視為一個樹狀結構的遍歷問題。每個節點代表一個動物，節點之間的父子關係由輸入定義。從根節點（動物 0）開始，使用深度優先搜尋 (DFS) 遍歷整個樹。在每個節點，根據題目描述的規則，將杯子蛋糕分發給左右子節點，並更新每個節點擁有的杯子蛋糕數量。由於分發的數量是均分，因此可以視為一種貪心策略。
複雜度分析
- 時間複雜度: O(N)，其中 N 是動物的數量。因為 DFS 遍歷了樹中的每個節點一次。
- 空間複雜度: O(N)，主要來自於
tr陣列，用於儲存每個動物的資訊。此外，DFS 的遞迴呼叫堆疊在最壞情況下可能達到 O(N) 的深度。
程式碼
#include <iostream>
using namespace std;
int n,tr[15][3],k;
void dfs(int p){
if(p==-1||(tr[p][0]+tr[p][1]==-2)||tr[p][2]==0)return;
if(tr[p][0]!=-1&&tr[p][1]!=-1){
tr[tr[p][0]][2]+=tr[p][2]/3;
tr[tr[p][1]][2]+=tr[p][2]/3;
tr[p][2]=tr[p][2]/3+tr[p][2]%3;
dfs(tr[p][0]);
dfs(tr[p][1]);
}
else if(tr[p][0]!=-1){
tr[tr[p][0]][2]+=tr[p][2]/2;
tr[p][2]=tr[p][2]/2+tr[p][2]%2;
dfs(tr[p][0]);
}
else{
tr[tr[p][1]][2]+=tr[p][2]/2;
tr[p][2]=tr[p][2]/2+tr[p][2]%2;
dfs(tr[p][1]);
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> tr[0][2];
for(int i=0;i<n;++i){
cin >> k >> tr[k][0] >> tr[k][1];
}
dfs(0);
for(int i=0;i<n;++i){
cout << tr[i][2] << " ";
}
}