Balancing Inversions

题目描述

Bessie 和 Elsie 在一个长度为 $2N$ 的布尔数组 $A$ 上玩游戏（$1 \leq N \leq 10^5$）。Bessie 的得分为 $A$ 的前一半中的逆序对数量，Elsie 的得分为 $A$ 的后一半中的逆序对数量。逆序对指一对下标满足 $i<j$ 的元素 $A[i]=1$ 与 $A[j]=0$。 例如，一个由一段 0 后接一段 1 组成的数组没有逆序对；而一个由 $X$ 个 1 后接 $Y$ 个 0 组成的数组有 $XY$ 个逆序对。 Farmer John 偶然发现了这个游戏棋盘，并想知道需要进行的最少相邻元素交换次数，使得这局游戏看起来像是平局。请帮助 Farmer John 计算这个问题的答案。

输入格式

第一行输入包含 $N$，第二行包含 $2N$ 个整数，且每个整数要么为 0，要么为 1。

输出格式

请输出使游戏打成平局所需的相邻交换次数。

5
0 0 0 1 0 1 0 0 0 1

1

提示

在这个例子中，数组的前一半初始有 $1$ 个逆序对，后一半有 $3$ 个逆序对。在将第 $5$ 位与第 $6$ 位的比特交换后，两个子数组的逆序对数量都变为 $0$。 题目作者：Dhruv Rohatgi

标签: USACO|2019|Gold

来源

USACO|2019|Gold