[白俊2805]木を切る

4889 ワード
Algorithm Problem Solving テキストリンク

[白俊2805]木を切る


第一の考え


木を降順に並べて、上から下へ削って、削った数まで数えます.
最大ツリー(0番インデックス)が最大ツリー(1番インデックス)より小さい場合、ターゲットインデックスは1増加します.
ターゲットインデックスが0でない場合、ターゲットインデックスのツリーが次のインデックスのツリーより大きい場合、ターゲットは0に戻ります.
任意の数のツリーが得られると、0番目のインデックスのツリー長はカッターの最小高さになります.

Java Code

package algo.study.thisweek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Acmicpc_2805_나무자르기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.valueOf(st.nextToken()); // 나무의 수
		int M = Integer.valueOf(st.nextToken()); // 최대 나무길이
		
		Integer[] trees = new Integer[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			trees[i] = Integer.valueOf(st.nextToken());
		}
		
		Arrays.sort(trees, Collections.reverseOrder());
		
		int answer = 0;
		int cnt = 0;
		int pointer = 0;
		if(N == 1) {
			answer = trees[0] - M;
		}else {
			while(cnt < M) {
				if(pointer == 0) {
					if(trees[pointer] >= trees[pointer+1]) {
						trees[pointer]--;
						cnt++;
					}else {
						pointer++;
					}
				}else {
					if(trees[pointer-1] < trees[pointer]) {
						trees[pointer]--;
						cnt++;
					}else {
						if(trees[pointer] < trees[pointer+1]) {
							pointer++;
						}else {
							pointer = 0;
						}
					}
				}
			}
			
			answer = trees[0];
		}
		
		System.out.println(answer);
	}

}

タイムアウト



バイナリ・ナビゲーションによるアクセス


木を1本ずつ切り落とすのではなく、カッターの長さで二分探索.
中間値は、最も高いツリーに対してカッター高さ(mid)として初めて決定されます.
得られた値が多ければ等しい場合、startはmid+1に上昇する.
startが高いほど、カッターの高さが高くなり、得られる木の長さが短くなります.
得られた値が少なければendはmid−1に減少する.

バイナリサーチ

  • 資料センター項目のキー値と比較して、次の検索の場所を特定して検索を継続する方法
  • 目的キーが見つかるまでループでバイナリ検索を行い、検索範囲を半分に絞り込みながら検索をより速く行う
  • バイナリ探索を行うためには資料を整理しなければならない.
  • 検索手順
  • 資料中央の要素を選択する.
  • 中央要素の値と探している目標値を比較します.
  • 中央要素の値と探している目標値が一致すれば探索を終了する.
  • ターゲット値が中央要素の値より小さい場合は、資料の左半分に対して新規検索を実行し、大きい場合は、資料の右半分に対して新規検索を実行する.
  • 検索する値が見つかるまで、上記の手順を繰り返します.

    • エラー


    得られたツリーの長さはint範囲を超えることが多い.
    成長金に両替して通過しました.

    Java Code

    package algo.study.thisweek;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Acmicpc_2805_나무자르기 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.valueOf(st.nextToken()); // 나무의 수
		int M = Integer.valueOf(st.nextToken()); // 최대 나무길이
		int max = Integer.MIN_VALUE;
		Integer[] trees = new Integer[N];
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			trees[i] = Integer.valueOf(st.nextToken());
			if(trees[i] > max) max = trees[i];
		}
		
		int start = 0; // 절단기 높이 값찾기의 시작
		int end = max; // 절단기의 최대 높이 = 나무의 최대 높이
		int answer = 0;
		
		while(start<=end) {
			int mid = (start+end) / 2; // 중간값을 절단기의 높이로!
			long sum = 0; // 얻어지는 나무길이
			for(int i=0; i<N; i++) {
				if(trees[i] > mid) {
					sum += trees[i] - mid;
				}
			}
			
			if(sum >= M) {
				start = mid+1;
				answer = mid;
			}else {
				end = mid-1;
			}
			
		}
		
		System.out.println(answer);
	}
}

    正解



    再帰二分ルックアップコード

    static int[] list = {1, 3, 5, 7, 9, 11, 14, 15, 18, 19, 25, 28};

// mid = 찾을 값의 인덱스
int search(int start, int end, int target) {
	if(start > end) return -1; //못찾음
	int mid = (start + end) / 2;
	if(list[mid] == target) return mid;
	else if(list[mid] > target) return search(start, mid - 1, target);
	else return search(mid + 1, end, target);
}
    centos 8 yumソースエラー問題
    Type Ahead