Elearning CodePath – CTP Online Judge

Ghép đống sỏi

BOCSOI13

🟢 Medium #Greedy #Priority Queue #Data Structure

### 📌 Thông tin chung

### Bài toán

Nhân dịp kỷ niệm ngày thành lập trường, Bé Bi tổ chức cho cả lớp chơi một trò chơi như sau:
Có $N$ đống sỏi xếp thành một hàng, đống thứ $i$ có $A_i$ viên sỏi. Ta có thể ghép hai đống sỏi bất kỳ thành một đống và mất một chi phí bằng 5% tổng số sỏi của hai đống đó.

Yêu cầu: Hãy 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í thực hiện là nhỏ nhất.

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

Dữ liệu vào từ file BOCSOI13.INP:
* Dòng 1: Số nguyên dương $N$.
* Dòng tiếp theo: Ghi $N$ số nguyên dương $A_1, A_2, \dots, A_n$, tương ứng là số lượng sỏi trong từng đống.

### Giới hạn

* $1 \le N \le 10^5$.
* Số lượng sỏi trong mỗi đống $A_i \le 10000$.

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

Ghi ra file BOCSOI13.OUT một số thực duy nhất là chi phí nhỏ nhất, lấy chính xác 2 chữ số sau dấu thập phân.

### ✨ Ví dụ

| BOCSOI13.INP | BOCSOI13.OUT |
| :--- | :--- |
| 4 <br> 10 11 12 13 | 4.60 |
| 2 <br> 1 1 | 0.10 |

### 🏷 Subtasks

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

✅ Đã AC: 8 / 23 submissions