2805번: 나무 자르기

이번 실수는 c++ 특, ll, int 실수했다.

만약 논리는 맞는데 틀린다면 이 부분을 봐야겠지.

2%에서 틀리길래 논리가 틀린건줄 알았다.

 

실버여도 방심하면 안되겠다

풀 문제 많구만

 

바이너리 서치 하라는 문제다.

O(M)이어도 시간초과라는 것에서부터 시작한다.

잘 뚫어지게 쳐다보다 보면

0부터 M까지 잘랐을 때 내림차순 정렬되어 있다는 것을 알 수 있다~

정렬이 되어있으면 할만한 것 중 하나가 바이너리 서치.

 

다만, 바이너리 서치를 그동안 STL에서 뽑아 쓰기만 했다면

이 문제에서 뒤통수 맞았을 것이다.

나처럼.

 

꼭! 시간이 되지 않더라도, 남지 않더라도 구현해보자.

언젠가 쓸 일이 오더라.

under_bound와 upper_bound 까지 세세하게 구현해보자!

#include <bits/stdc++.h>
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
#define mem(v, e) memset((v), (e), sizeof((v)))
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m;
vector<ll> tree;
ll binarySearch(int start, int end) {
    if (start == end) return start;
    int mid = (start + end) / 2;
    if (mid == start) return mid;
    ll sumMid = 0;
    for (int i = 0; i < n; i++) {
        if (tree[i] <= mid) continue;
        sumMid += tree[i] - mid;
    }
    if (sumMid < m) {
        return binarySearch(start, mid);
    }
    else {
        return binarySearch(mid, end);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    int maximum = 0;
    for (int i = 0; i < n; i++) {
        int in;
        cin >> in;
        maximum = max(maximum, in);
        tree.push_back(in);
    }
    cout << binarySearch(0, maximum);
}
/*
1 1
300

1 300
300

2 5
4 4

3 7
3 3 3

3 30
12 12 12

3 30
11 11 11

3 30
10 10 10

3 31
12 12 12
*/