阿祁的部落格

ZeroJudge f163-貨物分配 解題心得( 題目 )

解題概念:遞迴

解題方法:這題其實就是一連串遞迴，先遞迴求左右分別的重量以利比較，接著放貨物的時候就遞迴放貨物放到葉節點。

注意:這題要使用自己寫的方式輸入不能使用readline().split(" ")，否則很容易MLE (感謝jam930725@gmail.com(浮沉沉沉沉沉沉沉沉)提醒)

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

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

//Date:2021/10/06

import java.io.*;

public class zjf163 {

   public static int ret,r,w,n,m;
 
   public static int[] ow,nw;//ow原重、nw新的貨物重
 
   public static int[][] node,cw;//記錄節點、目前重量
 
   public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
 
   public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
 
   public static void main(String[] args) throws IOException {
 
       n=readnum();
 
       m=readnum();
 
       ow=new int[n];
 
       nw=new int[m];
 
       node=new int[n][2];
 
       cw=new int[n][2];
 
       for(int i=0;i<n;i++)ow[i]=readnum();
 
       for(int i=0;i<m;i++)nw[i]=readnum();
 
       int f;
 
       for(int i=0;i<n-1;i++) {
 
           f=readnum();
 
           node[f][0]=readnum();//左子節點
 
           node[f][1]=readnum();//右子節點
 
       }
 
       setup(1);
 
       for(int i=0;i<m;i++) {
 
           w=nw[i];
 
           put(1);
 
       }
 
       bw.flush();
 
   }
 
   
 
   public static int readnum() throws IOException {//輸入
 
       ret=0;
 
       r=br.read();
 
       while(r>47&&r<58) {
 
           ret*=10;
 
           r-=48;
 
           ret+=r;
 
           r=br.read();
 
       }
 
       return ret;
 
   }
 
   
 
   public static int setup(int x) {//前置作業
 
       if(x>=n) {
 
           return ow[x-n];
 
       }
 
       cw[x][0]=setup(node[x][0]);//左邊重
 
       cw[x][1]=setup(node[x][1]);//右邊重
 
       return cw[x][0]+cw[x][1];//總重
 

   }
 
   
 
   public static void put(int x) throws IOException {//放貨物
 
       if(x>=n) {
 
           bw.write(x+" ");//走到貨櫃輸出
 
           return;
 
       }
 

       if(cw[x][0]<=cw[x][1]) {
 
           cw[x][0]+=w;
 
           put(node[x][0]);
 
       }
 
       else {
 
           cw[x][1]+=w;
 
           put(node[x][1]);
 
       }
 
   }

}