Elearning CodePath – CTP Online Judge

Tối ưu hóa Tổng Bình Phương Hiệu

Minimum_Square

🟢 Easy

### 📝 Bài toán

Cho hai mảng số nguyên $A = (a_1, a_2, \dots, a_n)$ và $B = (b_1, b_2, \dots, b_n)$, có cùng độ dài $N$.

Giá trị $E$ giữa hai mảng được định nghĩa là tổng bình phương hiệu của các phần tử tương ứng:
$$
E = \sum_{i=1}^{N} (a_i - b_i)^2
$$

Ta được phép thực hiện $K_1$ thao tác trên mảng $A$ và $K_2$ thao tác trên mảng $B$. Tổng số thao tác là $K = K_1 + K_2$.
Trong một thao tác, ta chọn một phần tử bất kỳ trong mảng (hoặc $A$ hoặc $B$) và **tăng hoặc giảm** phần tử đó đi $1$ đơn vị.

Yêu cầu: Tìm giá trị $E$ nhỏ nhất có thể đạt được sau khi thực hiện **đúng** $K_1$ thao tác trên mảng $A$ và **đúng** $K_2$ thao tác trên mảng $B$.

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

* Dòng đầu tiên: Ba số nguyên $N$, $K_1$, $K_2$.
* Dòng thứ hai: $N$ số nguyên $a_1, a_2, \dots, a_n$.
* Dòng thứ ba: $N$ số nguyên $b_1, b_2, \dots, b_n$.

Giới hạn:
* $1 \le N \le 10^5$.
* $0 \le K_1 + K_2 \le 10^3$.
* $0 \le K_1, K_2$.
* $|a_i| \le 10^6$, $|b_i| \le 10^6$.

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

In ra một số nguyên duy nhất là giá trị nhỏ nhất của $E$ sau khi thực hiện đúng $K_1$ thao tác trên $A$ và đúng $K_2$ thao tác trên $B$.

---
### ✨ Ví dụ

| Input (`Emin.inp`) | Output (`Emin.out`) |
| :--- | :--- |
| `2 1 0` <br> `1 2` <br> `2 2` | `0` |

Giải thích: $N=2, K_1=1, K_2=0$. $A=[1, 2], B=[2, 2]$. $K=1$.
* Ban đầu: $D=[|1-2|, |2-2|] = [1, 0]$. $E = 1^2 + 0^2 = 1$.
* Thao tác 1 (tăng/giảm $A_i$): Chọn $A_1$ (vì $|1-2|=1$ là lớn nhất).
* Tăng $A_1$ lên 1: $A_1 \to 2$. $A=[2, 2]$. $D=[|2-2|, |2-2|] = [0, 0]$.
* $E_{\min} = 0^2 + 0^2 = 0$.

---
### 🏷 Phân Subtask

Do $K = K_1 + K_2$ rất nhỏ ($\le 10^3$), thuật toán tham lam $O(K \log N)$ là hiệu quả. Subtask chỉ khác nhau ở giới hạn $N$.

| Subtask | Ràng buộc | Số điểm ước tính | Gợi ý Thuật toán |
| :--- | :--- | :--- | :--- |
| 1 | $N \le 10^3$ | $40\%$ | Thuật toán Tham lam $O(N \log N + K \log N)$. |
| 2 | $N \le 10^5$ | $60\%$ | Thuật toán Tham lam $O(N \log N + K \log N)$ (Sắp xếp ban đầu và dùng Min-Heap/Priority Queue). |

---

✅ Đã AC: 0 / 0 submissions