Elearning CodePath – CTP Online Judge

Vào Nhà Hàng

KTABLES

🟢 Easy #Greedy

### 📌 Thông tin chung

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

Nhà hàng có $N$ bàn ăn. Bàn thứ $i$ có hai loại giá:
* $a_i$: giá phải trả nếu **đặt trước** bàn $i$ (chỉ được đặt trước duy nhất một bàn).
* $b_i$: giá phải trả nếu **không đặt trước** bàn $i$.

Yêu cầu: Với mỗi số lượng bàn ăn $k$ từ $1$ đến $N$, hãy tính số tiền ít nhất John phải trả nếu anh ta và bạn gái ăn ở **$k$ bàn**.

Tổng số tiền cho $k$ bàn được tính như sau:
$\text{Total Cost}_k = \min_{1 \le i \le N} \{ a_i + \sum_{j \in S, j \ne i} b_j \}$
trong đó $S$ là tập hợp $k$ chỉ số bàn được chọn ($|S|=k$), và $i$ là chỉ số bàn được đặt trước.

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

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

* Dòng đầu tiên: Chứa số $N$.
* $N$ dòng tiếp theo: Chứa $a_i$ và $b_i$ là giá đặt trước và giá không đặt trước của bàn thứ $i$.

Giới hạn:
* $1 \le N \le 5 \times 10^5$.
* $1 \le a_i, b_i \le 10^9$.

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

Ghi ra file `KTABLES.OUT` gồm $N$ dòng. Dòng thứ $i$ là số tiền ít nhất phải trả nếu John ăn ở $i$ bàn.

---
### ✨ Ví dụ

| Input (`KTABLES.INP`) | Output (`KTABLES.OUT`) |
| :--- | :--- |
| `3` `10 5` `9 3` `10 5` | `9` `13` `18` |

Giải thích:
$N=3$. Các bàn $(a_i, b_i)$: $B_1(10, 5), B_2(9, 3), B_3(10, 5)$.

* $k=1$: John chỉ ăn 1 bàn. Bàn này phải được đặt trước.
    * $\min(a_1, a_2, a_3) = \min(10, 9, 10) = 9$. **Output: 9**.
* $k=2$: John ăn 2 bàn. 1 bàn đặt trước ($i$), 1 bàn không đặt trước ($j$).
    * Chọn $i=1$: $a_1 + \min(b_2, b_3) = 10 + \min(3, 5) = 13$.
    * Chọn $i=2$: $a_2 + \min(b_1, b_3) = 9 + \min(5, 5) = 14$.
    * Chọn $i=3$: $a_3 + \min(b_1, b_2) = 10 + \min(5, 3) = 13$.
    * $\min(13, 14, 13) = 13$. **Output: 13**.
* $k=3$: John ăn 3 bàn. 1 bàn đặt trước ($i$), 2 bàn không đặt trước.
    * Chọn $i=1$: $a_1 + b_2 + b_3 = 10 + 3 + 5 = 18$.
    * Chọn $i=2$: $a_2 + b_1 + b_3 = 9 + 5 + 5 = 19$.
    * Chọn $i=3$: $a_3 + b_1 + b_2 = 10 + 5 + 3 = 18$.
    * $\min(18, 19, 18) = 18$. **Output: 18**.

---
### 🏷 Subtask

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

---

✅ Đã AC: 0 / 0 submissions