BOJ2805 나무자르기 (매개변수탐색)

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

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

public class Main
{
    
    public static long[] wood;
    public static int n;
    public static int m;
    
    
    public static long search(){
        long l = 0l;
        long r = 1_000_000_000l;
        long h = 0l;
        while(l<=r){
            long mid = (l+r)/2;
            long sum = 0;
            for(int i=0; i<n;i++){
                if(wood[i]<=mid){
                    continue;
                }
                sum+=(wood[i]-mid);
            }
            
            if(sum>=m){
                l=mid+1;
                h=mid;
                
            }else{
                r=mid-1;
            }
            
        }
        
        return h;
    }
    
    
    
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    String[] input1 = br.readLine().split(" ");
	    String[] input2 = br.readLine().split(" ");
	    
	    n = Integer.valueOf(input1[0]);
	    m = Integer.valueOf(input1[1]);
		wood = new long[n];
		
		for(int i=0; i<n;i++){
		    wood[i] = Long.valueOf(input2[i]);
		}
		
		long ans = search();
		
		System.out.println(ans);
		
		
		
		
	}
}

 

import java.util.Scanner;

class Main
{
    static boolean isPossible(int[] heights, int cutHeight, int thresholdHeight) {
        long sum = 0;
        for (int h : heights)
            if (h > cutHeight) sum += h - cutHeight;
        return sum >= thresholdHeight;
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] h = new int[N];
        for (int i = 0; i < N; i++)
            h[i] = sc.nextInt();

        int l = 0, r = 1000000000, ans = -1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (isPossible(h, m, M)) {
                ans = m;
                l = m + 1;
            }
            else r = m - 1;
        }
        System.out.println(ans);
    }
}