[백준] 2805번

map + 이진탐색 콤보를 잘 쓰면 쉽게 해결이 가능하다는 것을 알 수 있었다.

범위가 주어졌을 때 사용할 수 있을 듯하다.

#include <iostream>
#include <map>

int main() {
    long n, m, left = 0, right = 0, mid = 0;
    std::cin >> n >> m;
    std::map<long, long> trees; // 높이 -> 개수
    for (int i = 0; i < n; i++) {
        long _height;
        std::cin >> _height;
        trees[_height]++;
        right = std::max(right, _height);
    }

    long total = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        total = 0;
        for (auto& p : trees) {
            if (p.first > mid) {
                total += (p.first - mid) * p.second;
            }
        }
        if (total >= m) {
            left = mid + 1;
        } else {
            right = mid-1;
        }
    }


    std::cout << right;

    return 0;
}