#2805. 나무 자르기

파라메트릭 서치를 이용하여 문제를 해결한다.

c++

int main() {

    vector<int> v;
    
    int n, m;
    cin >> n >> m;
    
    while(n--) {
        int x;
        cin >> x;
        v.push_back(x);
    }
    
    sort(v.begin(), v.end());
    
    int l = 0, r = v[v.size() - 1], answer;
    
    while(l <= r) {
        int mid = ( l + r ) / 2;
        long long sum = 0;
        
        for(int i=0; i<v.size(); i++) {
            if ( v[i] > mid ) {
                sum += ( v[i] - mid );
            }
        }
        
        if (sum >= m) {
            // 길이 충족
            answer = mid;
            l = mid + 1;
        } else {
            // 길이 충족 못함
            r = mid - 1;
        }
    }
    cout << answer;
}