Elearning CodePath – CTP Online Judge

GOPK

Gộp khối

🟢 Hard #Greedy #Queue #Priority Queue

### 📌 Thông tin chung

### Bài toán

Cho một dãy số gồm $N$ phần tử $a_1, a_2, \dots, a_N$ và một số nguyên dương $K$. Bạn cần thực hiện gộp các phần tử trong mảng cho đến khi chỉ còn lại duy nhất một phần tử.

Quy tắc thực hiện một thao tác gộp như sau:
1. Chọn ra $K$ phần tử có giá trị nhỏ nhất hiện có trong mảng. Nếu số phần tử còn lại ít hơn $K$, chọn toàn bộ các phần tử còn lại.
2. Thay thế các phần tử đã chọn bằng một phần tử duy nhất có giá trị bằng tổng của chúng.
3. Chi phí của mỗi thao tác được tính bằng hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất trong nhóm $K$ phần tử vừa chọn.

Yêu cầu:
* Tính giá trị của phần tử cuối cùng còn lại.
* Tính tổng chi phí nhỏ nhất để thực hiện quá trình gộp trên.

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

Dữ liệu vào từ file GOPK.INP:
* Dòng 1: Hai số nguyên dương $N$ và $K$.
* Dòng 2: $N$ số nguyên $a_1, a_2, \dots, a_n$ là giá trị ban đầu của các phần tử.

### Giới hạn

* $1 \le N \le 2 \cdot 10^5$.
* $2 \le K \le N$.
* $0 \le a_i \le 10^9$.

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

Ghi ra file GOPK.OUT gồm hai dòng:
* Dòng 1: Giá trị phần tử cuối cùng.
* Dòng 2: Tổng chi phí của tất cả các thao tác.

### ✨ Ví dụ

| GOPK.INP | GOPK.OUT |
| :--- | :--- |
| 4 2 <br> 1 2 3 4 | 10 <br> 3 |

**Giải thích ví dụ:**
* Lần 1: Chọn {1, 2}, tổng = 3, chi phí = 2 - 1 = 1. Mảng còn: {3, 3, 4}.
* Lần 2: Chọn {3, 3}, tổng = 6, chi phí = 3 - 3 = 0. Mảng còn: {6, 4}.
* Lần 3: Chọn {4, 6}, tổng = 10, chi phí = 6 - 4 = 2. Mảng còn: {10}.
* Tổng chi phí: 1 + 0 + 2 = 3.

### 🏷 Subtasks

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

✅ Đã AC: 1 / 13 submissions