Elearning CodePath – CTP Online Judge

Ghép Đống Sỏi Chi Phí Tối Thiểu

GHEP_ONG_SOI_CHI_PHI

🟢 Medium

### 📌 Thông tin chung

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

Cho $N$ đống sỏi, đống thứ $i$ có $A_i$ viên sỏi.

Ta thực hiện thao tác **ghép hai đống sỏi bất kỳ** thành một đống mới.
Chi phí cho mỗi lần ghép hai đống có tổng lượng sỏi là $S$ được tính là:
$$
\text{Chi phí} = 5\% \times S = 0.05 \times S
$$
Yêu cầu: Tìm cách ghép $N$ đống sỏi này thành một đống duy nhất sao cho **tổng chi phí** phải trả là nhỏ nhất.

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

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

* Dòng 1: Số nguyên dương $N$ (số lượng đống sỏi).
* Dòng 2: $N$ số nguyên dương $A_1, A_2, \dots, A_N$ (số lượng sỏi trong từng đống).

Giới hạn:
* $2 \le N \le 100,000$.
* $1 \le A_i \le 10,000$.

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

Ghi ra file `DONG.OUT` một số thực duy nhất là chi phí nhỏ nhất phải trả. Kết quả phải được làm tròn và ghi dưới dạng 2 chữ số sau dấu thập phân.

---
### ✨ Ví dụ

| Input (`DONG.INP`) | Output (`DONG.OUT`) |
| :--- | :--- |
| `4` <br> `10 11 12 13` | `4.60` |

Giải thích:
1. $H = \{10, 11, 12, 13\}$. $C_{\text{tổng}} = 0$.
2. **Lần 1:** Ghép $10, 11$. $S_1 = 21$. Chi phí: $0.05 \times 21 = 1.05$. $C_{\text{tổng}} = 1.05$. $H = \{12, 13, 21\}$.
3. **Lần 2:** Ghép $12, 13$. $S_2 = 25$. Chi phí: $0.05 \times 25 = 1.25$. $C_{\text{tổng}} = 1.05 + 1.25 = 2.30$. $H = \{21, 25\}$.
4. **Lần 3:** Ghép $21, 25$. $S_3 = 46$. Chi phí: $0.05 \times 46 = 2.30$. $C_{\text{tổng}} = 2.30 + 2.30 = 4.60$. $H = \{46\}$.
Kết quả: $4.60$.

---
### 🏷 Subtask

Thuật toán $O(N \log N)$ là cần thiết do $N$ lớn.

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

---

✅ Đã AC: 0 / 0 submissions