문제를 읽어보면 핵심은 다음과 같다.
절단기의 높이 H로 나무들을 쭉 잘랐을때 위쪽의 남은 부분을 우리가 가져가는 것이고, 이 가져가야 하는 최소 길이는 M이다. 이때, M이상 길이를 가져가지만 가장 M과 가깝도록 만들어주는 절단기의 높이 H를 구하는 것이다.

H의 높이가 커질수록 가져갈 수 있는 총합은 항상 줄어들 수 밖에 없다. 또한, 나무의 최대갯수는 100만개이므로 H의 높이가 1변할때마다 가져갈 수 있는 총합도 +-100만 정도밖에 움직이지 않는다.

이 문제는 흔한 이분탐색 유형 중 하나라고 생각하지만 자료형에 신경쓰지 않는다면 문제가 일어날 수 있다. 각 나무의 높이는 최대 10억이기 때문에 만약 M이 너무 작게 주어져서 H가 1과 근접하게 될 수 있고 이런 경우를 조사해야 한다면, 가져갈 나무의 높이를 구하는 sum변수의 자료형 범위를 넘어서 터질 수도 있다.
때문에 나는 sum을 Long타입으로 정하고, H에 대해서 가져갈 수 있는 길이를 구하다가 sum이 Int.MAX_VALUE를 넘으면 그만 탐색하도록 했다. 여기서 내가 약21억이라는 값을 기준으로 잡은 이유는 H의 1 변화당 +-100만씩 변할 수 있고, M의 최댓값은 20억이기 때문이다. 즉, 21억을 넘는다면 그것보다 합이 적은 H가 반드시 존재할 것이므로 left만 1올리고 다음걸 탐색해도 된다.

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val (N, M) = br.readLine().split(" ").map { it.toInt() }
    val trees = br.readLine().split(" ").map { it.toInt() }
    var result = 0

    var left = 0
    var right = 10_0000_0000
    while (left <= right) {
        val H = (left + right) / 2 // 절단기의 높이
        var sum = 0L
        var isOver = false
        for (i in 0 until N) {
            sum += Math.max(trees[i] - H, 0)
            if (sum > Int.MAX_VALUE) { // H의 높이가 1이 변한다고 해도 나무갯수가 100만개이므로 최대 +-100만씩밖에 못움직인다. 즉, 21억으로 해도 잡아낼 수 있다.
                isOver = true
                left = H + 1
                break
            }
        }

        if (isOver) {
            left = H + 1
            continue
        }

        if (sum >= M) {
            if (H > result) {
                result = H
            }
            left = H + 1
        } else {
            right = H - 1
        }
    }

    println(result)
}

시간복잡도는 주어진 나무의 수 N의 최댓값인 100만개를 잘라서 합을 구하는 시간인 100만과 이분탐색으로 탐색범위를 줄여나가는 log2의N 을 곱한 시간이다.
문제의 제한은 1초이므로 문제없다.
가지치기 로직을 넣었더니 시간이 꽤나 많이 줄어든 것 같다.

java로 24년 5월 24일 다시 풀음

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

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());
        int[] trees = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) trees[i] = Integer.parseInt(st.nextToken());

        int maxH = 0;
        int l = 0; // 나무 최소 높이
        int h = 10_0000_0000; // 나무의 최대 높이
        while (l <= h) {
            int mid = (l + h) / 2;
            long sum = 0;
            for (int i = 0; i < N; i++) {
                sum += Math.max(((long) trees[i]) - mid, 0l);
                if (sum > 20_0000_0000) break;
            }
            if (sum >= M || sum > 20_0000_0000) { // 조금 더 높여봐도 되겠다. 덜 가져가려고 시도해봐도 되겠다.
                maxH = Math.max(maxH, mid);
                l = mid + 1;
            } else {
                h = mid - 1;
            }
        }
        System.out.print(maxH);
    }
}