백준 2805 나무 자르기

<링크>

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

<소스코드>

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<stdio.h> int main() {     int t[1000000];     int N, M;     scanf("%d%d", &N, &M);     for (int i = 0; i < N; ++i)         scanf("%d", t + i);     int l = 0, r = 1000000000;     int ans = 0;     while (l <= r)     {         int m = (l + r) / 2;         long long s = 0;         for (int i = 0; i < N; ++i)             if (t[i] > m)                 s += t[i] - m;         if (s >= M)         {             ans = m;             l = m + 1;         }         else             r = m - 1;     }     printf("%d", ans); }

cs

<풀이>

이분탐색으로 찍어본 높이 하나당 모든 나무를 살펴봐야하기 때문에

시간복잡도는 

이 된다.

만약 벌어들인 나무가 M이상이면 높이를 더 높여봐야하고, 그럴때마다 답이 갱신된다.

M보다 못벌었으면 높이를 더 낮춰야한다.