Elearning CodePath – CTP Online Judge

Cửa hàng Pizza

TIME

🟢 Medium #Greedy #Priority Queue #Interval #Scheduling #Data Structure

### 📌 Thông tin chung

### Bài toán

Tại cửa hàng pizza của Mr. Hải Dương, thay vì phục vụ theo quy tắc "đến trước phục vụ trước", cửa hàng áp dụng tiêu chí phục vụ sao cho **tổng thời gian đợi trung bình của khách hàng là nhỏ nhất**.

* Mỗi khách hàng $i$ đến tại thời điểm $T_i$ và yêu cầu một loại bánh cần thời gian chế biến là $L_i$.
* Tại một thời điểm, lò nướng chỉ có thể nướng một chiếc bánh duy nhất.
* Thời gian chờ của một khách hàng được tính từ lúc khách hàng đến cho đến khi bánh được làm xong.
* Mr. Hải Dương không biết trước các yêu cầu trong tương lai. Tại bất kỳ thời điểm nào khi lò nướng rảnh, anh ta sẽ chọn một trong số các khách hàng đã có mặt tại cửa hàng để phục vụ.

Yêu cầu: Tính phần nguyên của thời gian chờ trung bình nhỏ nhất.

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

Dữ liệu vào từ file TIME.INP:
* Dòng 1: Số nguyên dương $N$ là số lượng khách hàng ($1 \le N \le 10^5$).
* $N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên dương $T_i$ và $L_i$ ($0 \le T_i, L_i \le 10^9$).

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

Ghi ra file TIME.OUT một số nguyên duy nhất là phần nguyên của giá trị trung bình (tổng thời gian chờ chia cho $N$).

### ✨ Ví dụ

| TIME.INP | TIME.OUT | Giải thích |
| :--- | :--- | :--- |
| 3 0 3 1 9 2 5 | 8 | - Khách 1 đến lúc 0, làm mất 3s. Xong lúc 3s (đợi 3s). - Lúc 3s, khách 2 (đến lúc 1) và khách 3 (đến lúc 2) đều đã ở đó. - Chọn khách 3 (làm 5s) trước vì $5 < 9$. Xong lúc 8s (đợi 8-2=6s). - Cuối cùng làm khách 2. Xong lúc 17s (đợi 17-1=16s). - TB: (3+6+16)/3 = 8.33... $\rightarrow$ Lấy 8. |

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | 40% |
| 2 | $N \le 10^5, T_i, L_i \le 10^9$ | 60% |

✅ Đã AC: 2 / 5 submissions