A785.Balancing Inversions--Gold

提高+/省选-

USACO

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

Bessie and Elsie were playing a game on a boolean array AA of length 2N2N (1N1051 \leq N \leq 10^5). Bessie's score was the number of inversions in the first
half of AA, and Elsie's score was the number of inversions in the second half
of AA. An inversion is a pair of entries A[i]=1A[i]=1 and A[j]=0A[j]=0 where i<ji<j.
For example, an array consisting of a block of 0s followed by a block of 1s
has no inversions, and an array consisting of a block of XX 1s follows by a
block of YY 0s has XYXY inversions.
Farmer John has stumbled upon the game board and is curious to know the
minimum number of swaps between adjacent elements needed so that the game
looks like it was a tie. Please help out Farmer John figure out the answer to
this question.

输入格式

The first line of input contains NN, and the next line contains 2N2N integers
that are either zero or one.

输出格式

Please write the number of adjacent swaps needed to make the game tied.

输入输出样例

  • 输入#1

    5
    0 0 0 1 0 1 0 0 0 1
    

    输出#1

    1
    

说明/提示

In this example, the first half of the array initially has 11 inversion, and
the second half has 33 inversions. After swapping the 55th and 66th bits
with each other, both subarrays have 00 inversions.

首页