WoodCutting Made Easy!

• Time : $O(nlogn + log(max(A_i) * log(n)))$
• Space : $O(n)$

int Solution::solve(vector<int> &A, int B) {
    sort(begin(A), end(A));
    vector<long long> psum{0};
    for(int i = 0; i < A.size(); i++) psum.push_back(psum.back() + A[i]);
    int l = 0, r = A.back(), res = -1;
    while(l <= r) {
        long long m = l + (r - l) / 2;
        long long p = lower_bound(begin(A), end(A), m) - begin(A);
        long long now = psum.back() - psum[p] - (A.size() - p) * m;
        if(now < B) r = m - 1;
        else {
            res = m;
            l = m + 1;
        }
    }

    return res;
}n