阿祁的部落格

ZeroJudge g309-傳遞杯子蛋糕 解題心得

解題策略:BFS(深度優先搜尋)

解題方法:這題利用BFS方式(使用Queue)從根結點開始往下分蛋糕，根據左右子節點是不是-1(沒兒子)來討論是一人、兩人又或者是分給三人。

Java參考程式(如果有更好意見可在下方留言，以做為本文章之補充，感謝!)

//Author:En Chi Tsung(欉恩祁)

//Date:2021/9/15

import java.io.*;

import java.util.*;

public class zjg309 {

    public static void main(String[] args) throws IOException {

       BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
       String[] in=br.readLine().split(" ");
 
       int n=Integer.parseInt(in[0]);

       int k=Integer.parseInt(in[1]);
 
       int[][] tree=new int[n][2];//樹(紀錄子節點)
 
       int[] cc=new int[n];//分得的蛋糕
 
       int id;
 
       for(int i=0;i<n;i++)cc[i]=0;//初始化
 
       for(int i=0;i<n;i++) {
 
           in=br.readLine().split(" ");
 
           id=Integer.parseInt(in[0]);
 
           tree[id][0]=Integer.parseInt(in[1]);//左節點
 
           tree[id][1]=Integer.parseInt(in[2]);//右節點
 
       }
 
       Queue<Integer> bfs=new LinkedList<>();
 
       bfs.add(0);//從0號節點開始
 
       cc[0]=k;//0號動物先分得指定蛋糕數k
 
       int p,l,r;
 
       int divide;
 
       while(!bfs.isEmpty()) {
 
           p=bfs.poll();
 
           l=tree[p][0];
 
           r=tree[p][1];
 
           if(l==-1&&r==-1) {
 
               //葉節點
 
               continue;
 
           }
 
           else if(l==-1) {
 
               //分給子節點
 
               bfs.add(r);
 
               divide=cc[p]/2;
 
               cc[p]=cc[p]%2+divide;
 
               cc[r]=divide;


            }
 
           else if(r==-1) {
 
               //分給子節點
 
               bfs.add(l);
 
               divide=cc[p]/2;
 
               cc[p]=cc[p]%2+divide;
 
               cc[l]=divide;
 
           }
 
           else {
 
               //三者皆有
 
               bfs.add(l);
 
               bfs.add(r);
 
               divide=cc[p]/3;
 
               cc[l]=divide;
 
               cc[r]=divide;
 
               cc[p]=cc[p]%3+divide;    
 
           }
 
       }
 
       //輸出
 
       System.out.print(cc[0]);
 
       for(int i=1;i<n;i++) {
 
           System.out.print(" "+cc[i]);
 
       }
 
   }

}