Elearning CodePath – CTP Online Judge

Eating Banana

BS014

🟢 Hard #General #Binary Search #Combinatorics #Interval #Optimization

### 📌 Thông tin chung

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

Cho $N$ thùng chuối, thùng thứ $i$ có $A[i]$ quả chuối. Nhóm của bạn có $K$ giờ để ăn tất cả các thùng chuối.

Quy tắc:
* Mỗi giờ, nhóm chỉ chọn **một thùng** để ăn.
* Số lượng chuối ăn mỗi giờ là một hằng số $X$.
* Nếu số chuối trong thùng nhỏ hơn hoặc bằng $X$, thì thùng đó sẽ được ăn hết trong 1 giờ.
* Nếu số chuối trong thùng lớn hơn $X$, thì nhóm ăn $X$ quả trong giờ đó, và số chuối còn lại sẽ được ăn trong các giờ tiếp theo (theo cùng quy tắc $X$ quả/giờ).
* **Mục tiêu:** Tìm số lượng chuối tối thiểu ($X_{\text{min}}$) phải ăn mỗi giờ để ăn hết tất cả chuối trong vòng $K$ giờ.

Thời gian $T_i$ cần để ăn hết thùng $A[i]$ với tốc độ $X$ quả/giờ là:
$T_i = \left\lceil \frac{A[i]}{X} \right\rceil$
Ta cần tìm $\min(X)$ sao cho:
$\sum_{i=1}^{N} \left\lceil \frac{A[i]}{X} \right\rceil \le K$

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

Dữ liệu vào từ file `BS_EatingBanana.inp` gồm 2 dòng:

* Dòng 1: Số nguyên $N$ (số thùng chuối) và $K$ (số giờ phải ăn hết).
* Dòng 2: $N$ số nguyên $A[i]$ là số chuối trong mỗi thùng, viết cách nhau 1 khoảng trắng.

Giới hạn:
* $1 \le N \le 10^5$.
* $N \le K \le 10^5$.
* $1 \le A[i] \le 10^4$.

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

Ghi ra file `BS_EatingBanana.out` một số nguyên là số chuối tối thiểu phải ăn trên mỗi giờ ($X_{\text{min}}$).

---
### ✨ Ví dụ

| Input | Output | Giải thích |
| :--- | :--- | :--- |
| `4 8` `3 6 7 11` | `4` | $N=4, K=8$. Tốc độ ăn tối thiểu $X=4$. Thùng 3: $\lceil 3/4 \rceil = 1$ giờ. Thùng 6: $\lceil 6/4 \rceil = 2$ giờ. Thùng 7: $\lceil 7/4 \rceil = 2$ giờ. Thùng 11: $\lceil 11/4 \rceil = 3$ giờ. Tổng thời gian: $1 + 2 + 2 + 3 = 8$ giờ. |

---
### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $N \le 10^3$; $K \le 10^3$; $A[i] \le 100$ | $30\%$ |
| $2$ | $N \le 10^5$; $K \le 10^5$; $A[i] \le 1000$ | $30\%$ |
| $3$ | $N \le 10^5$; $K \le 10^5$; $A[i] \le 10^4$ | $40\%$ |

---

✅ Đã AC: 10 / 27 submissions

📘 Lời giải

```
#include <bits/stdc++.h>
using namespace std;

//Tính số giờ với mid giả định
bool canFinish(int A[], int n, int k, int mid) { 
int hours = 0; 
 for (int i=0; i<n;i++) { 
 hours += (A[i] + mid - 1) / mid; // Tính số giờ cần để ăn thùng chuối này 
 } 
return hours <= k; // Kiểm tra xem có thể hoàn thành trong k giờ không
}

int minBananasPerHour(int A[], int n, int k) { 
int left = 1; // Số chuối tối thiểu 
int right = *max_element(A, A+n); // Số chuối tối đa trong một thùng 
int result = right; while (left <= right) { 
 int mid = (right + left) / 2; 
 if (canFinish(A, n, k, mid)) { 
 result = mid; // Nếu có thể hoàn thành, cập nhật kết quả 
 right = mid - 1; // Tìm số lượng chuối tối thiểu hơn 
 } 
 else { 
 left = mid + 1; // Tăng số lượng chuối 
 } 
} 
return result;
}

int main() { 
 int n, k;
 cin >> n>>k; 
 int A[n]; 
 for (int i = 0; i < n; i++) { 
 cin >> A[i]; 
 } 
 int result = minBananasPerHour(A,n,k); 
 cout << result; 
return 0;
}
```