厩舎の決定(決定アルゴリズム)

質問する

私の答え

import java.util.*;
class Main {
	//들어갈수있는 말 마릿수
	public int Count(int[] arr, int distance) {
		int cnt = 0;
		int ep = 0;
		for(int i=0; i<arr.length;i++) {
			//첫번째 말
			if(i == 0) {
				cnt++;
				ep = arr[i];
			}
			if(i>0 && arr[i]-ep >= distance) {
				cnt++;
				ep = arr[i];
			}
		}
		return cnt;
	}
	public int solution(int n, int c,int[] arr) {
		//n 마구간의 갯수/ c 말의 갯수/ arr 마구간좌표
		int answer = 0;
		Arrays.sort(arr);
		//lt = 거리의 최솟값이 될수있는값. rt = 거리의 최댓값이 될수있는값.
		int lt = 1, rt = arr[n-1];
		while(lt<=rt) {
			int mid = (lt+rt)/2;
			if(Count(arr, mid) >= c) {
				answer = mid;
				lt = mid +1;
			}
			else rt = mid -1;
		}
		
		return answer;
	}

		    
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int m = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) arr[i] = kb.nextInt();
		System.out.print(T.solution(n, m, arr));
	}
	
}

++Count関数の概要

	public int Count(int[] arr, int distance) {
		int cnt = 0;
		int ep = arr[0];
		for(int i=1; i<arr.length;i++) {
			if(i>0 && arr[i]-ep >= distance) {
				cnt++;
				ep = arr[i];
			}
		}
		return cnt;
	}

解答方法

前の問題と同じように違うようです.
ltを厩舎間距離の最大値1に設定します.
rtを厩舎間距離にできるarrの最末端要素として指定します.
mid(lt+rt)/2値から検索を開始し、count関数を作成し、中間距離の間隔を返し、最大何頭の馬がいるかを返します.
最初の文は常に最小の座標に含まれるので、cnt=1から始まります.
ep(すなわち、前馬の厩舎座標)はarr[0]から始まる.
(現在の厩舎の座標)-(すなわち前馬の座標)=前馬との距離
距離以上であれば、馬は厩舎に入ることができます.
cnt++になり、epは現在の厩舎座標になります.
厩舎に入る馬の数がc(目標番号)以上であれば、距離が増加できることを示すため、mid未満の値を検索する必要はなく、lt=mid+1となる.
そうでなければ、cより小さい場合は距離が大きすぎるため、midより大きい値を検索する必要がないため、rt=mid-1となる.
ドアが回転するにつれて、答えには最大距離が格納されます.

コアキー

今までltとrtがどんな値で始まるべきか分からなかった...
意思決定アルゴリズムでより多くの問題を解決しなければならない.