Thu hoạch gỗ (Tìm kiếm nhị phân trên đáp án)

Binary-search Buổi 06 — Sắp xếp & Tìm kiếm
Points
27
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
sortsearch
Submissions
Đề bài

Bác tiều phu cần chặt ít nhất $M$ mét gỗ từ $N$ cây có độ cao lần lượt là $H_1, H_2, \dots, H_N$. Bác đặt lưỡi cưa ở độ cao nguyên $H$: mọi cây cao hơn $H$ sẽ bị cắt phần ngọn cao hơn $H$ (thu được $H_i - H$ mét gỗ), các cây thấp hơn hoặc bằng $H$ không bị cắt. Hãy dùng tìm kiếm nhị phân để tìm độ cao $H$ lớn nhất sao cho tổng lượng gỗ thu được $\ge M$.

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $M$. Dòng thứ hai chứa $N$ số nguyên không âm $H_i$.

Dữ liệu ra

Một số nguyên duy nhất là độ cao $H$ lớn nhất.

Ví dụ
Input Output
4 7\n20 15 10 17 15
5 20\n4 42 40 26 46 36
Giới hạn

$1 \le N \le 10^5$, $1 \le M \le 10^{12}$, $0 \le H_i \le 10^9$, tổng các $H_i \ge M$.

Draft saved