Cân bằng nghịch thế

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho mảng nhị phân $A$ gồm $2 N$ phần tử. Một nghịch thế trong đoạn là cặp $(i, j)$ với $i < j$ , $A [i] = 1$ , $A [j] = 0$ . Gọi $invL$ là số nghịch thế trong nửa đầu ( $A [0 . . N - 1]$ ) và $invR$ là số nghịch thế trong nửa sau ( $A [N . .2 N - 1]$ ).

Tìm số phép hoán đổi hai phần tử liền kề tối thiểu để $invL = invR$ .

Dữ liệu vào

Dòng đầu: $N$ .
Dòng thứ hai: $2 N$ số nguyên $0$ hoặc $1$ .

Dữ liệu ra

Số phép hoán đổi tối thiểu.

Ràng buộc

$1 \leq N \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
5 0 0 0 1 0 1 0 0 0 1	1	invL=1, invR=3. Hoán đổi A[4] và A[5]: invL=0, invR=0.

Bình luận

Không có bình luận tại thời điểm này.