Elearning CodePath – CTP Online Judge

Xếp Hộp Tối Ưu

GEN005

🟢 Easy #Binary Search #Knapsack

### 📌 Thông tin chung

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

Cho $N$ sản phẩm với trọng lượng $a_1, a_2, \dots, a_N$. Các sản phẩm được xếp theo thứ tự vào các hộp có cùng dung lượng $M$.

**Quy tắc Xếp hộp:**
1. Sản phẩm được xếp lần lượt theo thứ tự $1, 2, \dots, N$.
2. Sản phẩm thứ $i$ được xếp vào hộp đang mở nếu trọng lượng $a_i$ không vượt quá dung lượng còn lại của hộp.
3. Nếu dung lượng còn lại không đủ, hộp hiện tại được đóng lại, xuất xưởng, và một hộp rỗng mới được mở ra để xếp sản phẩm $a_i$ vào.
4. Ban đầu có một hộp rỗng được mở sẵn.

Yêu cầu: Tìm giá trị **dung lượng hộp $M$ nhỏ nhất** sao cho tổng số hộp cần sử dụng để xếp hết $N$ sản phẩm **không vượt quá** số hộp cho trước $K$.

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

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

* Dòng 1: Chứa hai số nguyên $N$ và $K$.
* $N$ dòng tiếp theo: Mỗi dòng chứa một số nguyên dương $a_i$ (trọng lượng sản phẩm thứ $i$).

Giới hạn:
* $1 \le K \le N \le 10^5$.
* $1 \le a_i \le 30,000$.

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

Ghi ra file `ZXY.OUT` một số nguyên duy nhất là dung lượng $M$ nhỏ nhất của hộp.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions