白峻2805号です.
https://www.acmicpc.net/problem/2805

質問する

尚根は木Mメートルが必要です.近くで木を買う場所が壊れてしまったので、政府に伐採許可を申請しました.政府は尚勤があなたの家の近くの木を伐採することを許可し、尚勤は新しく買った木材切断機を使って木を救う.
木材切断機の動作は以下の通りです.まず、尚根はカッターに高さHを指定しなければならない.高さを指定した後、のこぎりは地面からHメートルまで登った.そして、一連の木を切り落とす.そのため、高さがHより大きい木は、H上の部分は切り落とされ、低いものは切り落とされません.例えば、1行連続した木の高さは20,15,10,17である.尚根が高さ15を指定すると、木を切った後の高さは15、15、10、15になりますが、尚根は5インチの木と2インチの木を持って家に帰ります.(合計7メートル)カッターで設定できる高さは正の整数またはゼロです.
尚根は環境に興味があるので、どれだけの木を家に持ち帰るかだけを考えていた.このとき、少なくともmメートルの木を持ち帰るために、カッターが設定できる高さの最値を求めるプログラムを作成してください.

入力

1行目は、木の数Nと、上根が持ち帰ろうとする木の長さMを与える.(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
2行目はツリーの高さを示します.木の高さの和はいつもM以上なので、常根はいつも家に必要な木を持っていくことができます.高さが10000000以下の整数または0.

考える

以前に解決した剪断網線問題とよく似ている.
アルゴリズムもバイナリ検索を使う点も同じです
最初はバイナリナビゲーションではなく、高いところから削る方式です.
範囲が広く、タイムアウトが発生しました.
コードを表示します.
バイナリ探索binary_searchはコアである.minは、最初はツリーの一番下の0の値、maxはツリーの一番高い値に設定されます.Collections.max(treeList)でtreeListで一番高い木が見つかりました.
バイナリ検索を実行するために、binary_search関数が追加されました.mid変数を使用して、私たちが探している切断位置を見つけます.midの値を切断位置に設定し、treeListの値がmidの値以上の樹木を順に選択して、その切断樹木の長さがsumの値と一致するまで切断する.

TMI

初めてこの問題を作ったとき、意外に広い範囲の探索をしようとした.
問題を見て、どんなアルゴリズムを使うかという目を養う必要がある.
これは前に解決した網を切る問題とよく似ていると思いますが.
バイナリ探索の私を思い出せない...
元気を出してください!!!

コード#コード#

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		List<Long> treeList = new ArrayList<>();

		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			treeList.add(Long.parseLong(st.nextToken()));
		}

		long min = 0;
		long max = Collections.max(treeList);
		long result = 0;

  		// 최대 높이 이진 탐색.
		result = binary_search(M, min, max, treeList);
		System.out.println(result);
	}

	// 이진 탐색.
	private static long binary_search(int M, long min, long max, List<Long> list) {
	
		long mid = 0;
		while(min <= max) {
			long sum = 0;

			for(long tree : list) {
				if(tree >= mid) {
					sum += tree - mid;					
				}	
			}

			if(sum >= M) {
				min = mid + 1;
            }
			else {
				max = mid - 1;
			}

			// mid값이 결국 우리가 찾는 절단기에 설정할 수 있는 높이의 최댓값
			mid = (max + min)/2;

		}

		return mid;

	}// End Main

} // End Class