Elearning CodePath – CTP Online Judge

Hợp nhất Phần tử và Chi phí

Expense_Merging

🟢 Easy #Array #Knapsack

### 📝 Bài toán

Cho một dãy số $A$ gồm $N$ phần tử $A = (a_1, a_2, \dots, a_n)$ và một số nguyên dương $K$.

Ta thực hiện lặp lại một thao tác cho đến khi trong mảng còn đúng một phần tử:

1. **Thao tác Hợp nhất:** Chọn ra $\min(K, |A|)$ phần tử nhỏ nhất trong mảng $A$.
2. **Thay thế:** Thay thế các phần tử đã chọn bằng **tổng** của chúng.
3. **Chi phí:** Chi phí cho lần thực hiện này là **hiệu** của số lớn nhất và số nhỏ nhất trong số $\min(K, |A|)$ phần tử vừa chọn.

Yêu cầu:
1. In ra giá trị của phần tử cuối cùng còn lại trong mảng.
2. In ra **tổng chi phí** thực hiện qua tất cả các lần thao tác.

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

* Dòng đầu tiên: Hai số nguyên dương $N$ và $K$.
* Dòng tiếp theo: $N$ số nguyên $a_1, a_2, \dots, a_n$ cách nhau bởi dấu cách.

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

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

* Dòng đầu tiên: Phần tử cuối cùng xuất hiện trong mảng (tổng của tất cả $A_i$).
* Dòng thứ hai: Tổng chi phí thực hiện.

---
### ✨ Ví dụ

| Input (`Expense.inp`) | Output (`Expense.out`) |
| :--- | :--- |
| `4 2` <br> `1 2 3 4` | `10` <br> `3` |

Giải thích:
* Ban đầu: $A = [1, 2, 3, 4]$. Tổng chi phí $T=0$.
* **Lần 1:** Chọn $\min(2, 4) = 2$ phần tử nhỏ nhất: $\{1, 2\}$.
    * Chi phí: $2 - 1 = 1$. $T=1$.
    * Tổng mới: $1 + 2 = 3$.
    * Mảng mới: $[3, 3, 4]$.
* **Lần 2:** Chọn 2 phần tử nhỏ nhất: $\{3, 3\}$.
    * Chi phí: $3 - 3 = 0$. $T=1+0=1$.
    * Tổng mới: $3 + 3 = 6$.
    * Mảng mới: $[4, 6]$.
* **Lần 3:** Chọn 2 phần tử nhỏ nhất: $\{4, 6\}$.
    * Chi phí: $6 - 4 = 2$. $T=1+2=3$.
    * Tổng mới: $4 + 6 = 10$.
    * Mảng mới: $[10]$.
* Dừng. Phần tử cuối: $10$. Tổng chi phí: $3$. (Kết quả ví dụ: $10$ và $3$)

---
### 🏷 Phân Subtask

Do $N$ lớn ($2 \cdot 10^5$), thuật toán cần có độ phức tạp $O(N \log N)$. Số lần thao tác là $O(N)$.

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

✅ Đã AC: 0 / 0 submissions