[USACO19OPEN] Balancing Inversions G
题目描述
Bessie和Elsie在一个长为 $ 2N $ 的布尔数组 $ A $ 上玩游戏( $ 1 \leq N \leq 10^5 $ )。Bessie的分数为 $ A $ 的前一半的逆序对数量,Elsie的分数为 $ A $ 的后一半的逆序对数量。逆序对指的是满足 $ A[i]=1 $ 以及 $ A[j]=0 $ 的一对元素,其中 $ i<j $ 。例如,一段0之后接着一段1的数组没有逆序对,一段 $ X $ 个1之后接着一段 $ Y $ 个0的数组有 $ XY $ 个逆序对。
Farmer John偶然看见了这一棋盘,他好奇于可以使得游戏看起来成为平局所需要交换相邻元素的最小次数。请帮助Farmer John求出这个问题的答案。
输入输出格式
输入格式
输入的第一行包含 $ N $ ,第二行包含 $ 2N $ 个为0或1的整数。
输出格式
输出使得游戏成为平局最少需要的移动次数。
输入输出样例
输入样例 #1
5
0 0 0 1 0 1 0 0 0 1
输出样例 #1
1
说明
在这个例子中,初始时前一半有1个逆序对,后一半有3个逆序对。交换了第5和第6个数之后,两个子数组均有0个逆序对。