Elearning CodePath – CTP Online Judge

Cưa Gỗ

GEN003

🟢 Medium #Binary Search

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho $N$ cây với độ cao tương ứng là $a_1, a_2, \dots, a_N$. Ta cần thu thập ít nhất $M$ mét gỗ.

Ta đặt lưỡi cưa ở độ cao $H$ (mét).
* Cây thứ $i$ sẽ bị cưa nếu $a_i > H$.
* Lượng gỗ thu được từ cây $i$ là $a_i - H$.
* Tổng lượng gỗ thu được $G(H)$ là:
$G(H) = \sum_{i=1}^{N} \max(0, a_i - H)$

Yêu cầu: Tìm giá trị số nguyên $H$ lớn nhất sao cho tổng lượng gỗ thu được $G(H)$ lớn hơn hoặc bằng $M$ ($G(H) \ge M$).

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `WOOD.INP`:

* Dòng 1: Ghi hai số nguyên dương $N$ và $M$.
* Dòng 2: Ghi $N$ số nguyên dương $a_1, a_2, \dots, a_N$ cách nhau bởi dấu cách.

Giới hạn:
* $1 \le N \le 10^6$.
* $1 \le M \le 2 \times 10^9$.
* $1 \le a_i \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `WOOD.OUT` một số nguyên duy nhất là giá trị $H$ lớn nhất cần tìm.

---
### Ví dụ

| WOOD.INP | WOOD.OUT |
| :--- | :--- |
| `4 7` <br> `20 15 10 18`  | `15` |

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000, M \le 10^6$ | $30\%$ | 
| 2 | $N \le 10^6, a_i \le 10^9$ | $70\%$ |

---

✅ Đã AC: 8 / 15 submissions