Elearning CodePath – CTP Online Judge

Đổi chỗ tối thiểu để gộp số 1

MINGROUP1

🟢 Easy #Prefix Sum #Sliding Window #Interval

### 📌 Thông tin chung

---
### 📝 Định nghĩa

Cho dãy số $A$ chỉ gồm các số có giá trị $0$ hoặc $1$.

Mục tiêu là sau khi đổi chỗ các phần tử, tất cả các số $1$ trong dãy sẽ nằm trong một miền liên tiếp (tạo thành một khối $1$ liên tục).

---
### 📝 Yêu cầu

Hãy đếm **số lượt đổi chỗ ÍT NHẤT** các phần tử để đạt được mục tiêu trên.

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

* Dòng 1 gồm số nguyên $N$ chỉ số phần tử thuộc dãy ($1 \le N \le 10^6$).
* Dòng 2 gồm $N$ số nguyên chỉ mảng $A$ (các phần tử cách nhau bởi dấu cách).

Giới hạn:
* $1 \le N \le 10^6$.
* $A_i \in \{0, 1\}$.

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

Số lượt đổi chỗ ít nhất.

---
### ✨ Ví dụ

| MINGROUP1.inp | MINGROUP1.out |
| :---: | :---: |
| `5` <br> `1 0 1 0 1` | `1` |
| `6` <br> `1 0 1 0 1 1` | `1` |

---
### 🏷 Ràng buộc

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

---

✅ Đã AC: 0 / 0 submissions