Java의 균형 잡힌 시스템 파일 파티션 솔루션

의문

시스템 디스크 파티션의 디렉터리 구조는 트리로 표시됩니다. n개의 디렉토리는 0에서 n-1까지 번호가 매겨져 있으며 루트 디렉토리의 번호는 0입니다. 트리의 구조는 상위 배열에 의해 정의됩니다. 여기서 parent[i] = j는 디렉토리 i가 다음의 직접 하위 디렉토리임을 의미합니다. 제이. 루트 디렉터리에는 부모가 없으므로 부모[0] = -1로 표시됩니다. files_size[i]의 값은 하위 디렉토리를 제외하고 디렉토리 i에 있는 파일의 크기 합계를 킬로바이트 단위로 나타냅니다. 디렉토리 내용의 크기는 모든 하위 디렉토리의 크기로 정의됩니다. 결과 하위 트리의 크기가 가능한 한 가까워지도록 하나의 가지를 잘라서 트리를 두 개의 작은 트리로 분할합니다.

예 부모 = [-1,0,0,1,1,2] files_size = [1,2,2,1,1,1]

시스템의 구조는 아래 다이어그램에 나와 있습니다. 노드는/로 레이블이 지정됩니다. -> 이미지 파일

디렉토리 1과 0 사이의 분기를 잘라냅니다. 파티션 {0,2,5}의 크기는 files_size[0] + files_size[2] + files_size[5] = 1 + 2 + 1 = 4입니다. 파티션 {1,3, 4}의 크기는 files_size[1] + files_size[3] + files_size[4] = 2 + 1 + 1 = 4입니다. 두 개의 새 트리 크기의 절대 차이는 4 - 4 = 0입니다. 절대 차이가 더 작은 경우 최종 답은 0입니다.

함수 설명 아래 편집기에서 mostBalancedPartition 함수를 완성합니다.

이 함수는 다음 매개변수를 가집니다. int parent[n]: 각 parent[i]는 디렉토리 i의 상위 디렉토리입니다. int files_size[n]: 각 file_sizes[i]는 디렉토리 i의 파일 크기 합계입니다.

반환 int: 두 하위 트리 간 콘텐츠 크기의 최소 절대 차이

제약 조건 2 <= n <= 10^5 1 <= files_size[i] <= 10^4 parent[0] = -1 parent[i] < i for 1 <= i < n 각 디렉토리 트리의 깊이는 대부분 500.

샘플 입력 부모 = [-1,0,1,2] files_size = [1,4,3,4] 샘플 출력 2 샘플 입력 부모 = [-1,0,0,0] files_size = [10,11,10 ,10] 샘플 출력 19

해결책

`
import java.util.*;
공개 클래스 BalancedFileSystem {

public static int balencedFile(int[] p,int[] f,int n)
{
    int[] t = new int[n];
    int cur;
     int temp=0;
    for(int i=0;i<n;i++)
    {
        cur=i;
        while(cur!=-1)
        {
            t[cur]+=f[i];
            cur=p[cur];
        }
    }
    int val = Math.abs(t[0]-2*t[1]);
     for(int i=1;i<n;i++)
     {
        temp = Math.abs(t[0]-2*t[i]);
        if(val>temp)
        {
           val = temp;
        }
     }
     return val;
}

public static void main(String[] args)
{
    Scanner sc= new Scanner(System.in);
    System.out.println("enetr the size of array");
    int n=sc.nextInt();
    int[] p= new int[n];
    int[] f = new int[n];
    System.out.println("enetr the parent array");
    for(int i=0;i<n;i++)
    {
        p[i]=sc.nextInt();
    }
    System.out.println("enetr the file size array");
    for(int i=0;i<n;i++)
    {
        f[i]=sc.nextInt();
    }
    int ans = balencedFile(p,f,n);
    System.out.println("ans :" +ans);

    sc.close();
}

}

`

p는 상위 배열입니다.
f는 파일 크기 배열입니다.