[伯俊/Java]1654ケーブルを切る

2578 ワード
コーディングテスト テキストリンク

条件


  • 所有するネットワークケーブルの数はKです.

  • 必要なケーブル数はNです.

  • ローカルエリアネットワーク線の最大値はint型の最大値であるためlongにナビゲートする.

  • K本のローカルネットワーク線の長さを受け入れ、その値を満たすために必要なN本を、最大長のローカルネットワーク線を出力すればよい.

    • 入力例



    解説


    ローカルエリアネットワーク線の最小長さから最大長さまでの範囲を使用して、2分の1ナビゲーションで使用/を試み、数の要件を満たす場合は長さの値を保存し、L<=Rまで2分の1ナビゲーションを実行します.
    また,最終的に格納される値は個数の最大長を満たすローカルエリアネットワークであり,格納値を出力すると正解が得られる.

    コード#コード#

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



public class Main {
	
	static int K,N;
	static int[] A;
	
	
	static FastReader scan = new FastReader();
	static StringBuilder sb = new StringBuilder();

	static void input() {
		
		K = scan.nextInt(); // 가지고 있는 랜선의 개수를 받는다.
		N = scan.nextInt(); // 필요로 하는 랜선의 개수를 받는다.
		A = new int[K+ 1]; //index 시작을 1로 하기 위해 N+1을 해준다.
		for(int i=1;i<=K;i++) { //K의 값들을 받아준다.
			A[i] = scan.nextInt(); 
		}
	
	}

	
	static boolean findAns(long len) {
		long sum =0;
		for(int i = 1;i<=K;i++) {
			sum +=  A[i] / len; // 이분 탐색으로 정해진 값에서 가진 랜선의 길이들을 나							   // 눠 필요로 하는 개수가 충족되는지를 확인한다.
		}
		return sum >= N;

	}
	
	static void find() {
		long L = 1, R = Integer.MAX_VALUE,ans=0; // 이분 탐색 범위를 정해준다.
		while(L<=R) {
			long mid = (R + L) /2;
			if(findAns(mid)) { // 개수를 충족한다면 해당 값은 ans에 저장후 다음 이분탐								// 색을 시작한다.
				ans = mid;
				L = mid +1;
			}else {
				R = mid - 1;
			}
		}
		System.out.println(ans); // 저장되어 있는 mid값을 출력한다.
		}

		
		
	public static void main(String[] args) {
		input();
		find();
	}
	
	static class FastReader{
		BufferedReader br;
		StringTokenizer st;
		
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public FastReader(String s) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(new File(s)));
		}
		
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		Long nextLong() {
			return Long.parseLong(next());
		}
		double nextDouble(){
			return Double.parseDouble(next());
		}
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			}catch(IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}
}
    The Result of an Interesting and Useful Program on Floating Numbers
    JPA学習ノート-一方向多対一の関連関係をマッピングする