BZPRO
#5558. [Usaco2019 Open]Balancing Inversions
内存限制：256 MiB
时间限制：10 Sec
提交
提交记录
讨论
题目描述
Bessie和Elsie在一个长为2N的布尔数组A上玩游戏（1≤N≤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的整数。
输出格式
输出使得游戏成为平局最少需要的移动次数。
样例
样例输入
5
0 0 0 1 0 1 0 0 0 1
样例输出
1
在这个例子中，初始时前一半有1个逆序对，后一半有3个逆序对。交换了第5和第6个数之后，两个子数组均有0个逆序对。
数据范围与提示
BZPRO