USACO 2019 US Open Contest, Gold Problem 3. Balancing Inversions

Category: 國(guó)際競(jìng)賽 Date: 2019年5月17日下午6:50

Bessie and Elsie were playing a game on a boolean array AA of length 2N2N (1≤N≤1051≤N≤105). 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.

INPUT FORMAT (file balance.in):

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

OUTPUT FORMAT (file balance.out):

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

SAMPLE INPUT:
5
0 0 0 1 0 1 0 0 0 1

SAMPLE OUTPUT:
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.
Problem credits: Dhruv Rohatgi

中文版

Bessie和Elsie在一個(gè)長(zhǎng)為2N2N的布爾數(shù)組AA上玩游戲（1≤N≤1051≤N≤105）。Bessie的分?jǐn)?shù)為AA的前一半的逆序?qū)?shù)量，Elsie的分?jǐn)?shù)為AA的后一半的逆序?qū)?shù)量。逆序?qū)χ傅氖菨M足A[i]=1A[i]=1以及A[j]=0A[j]=0的一對(duì)元素，其中i<ji<j。例如，一段0之后接著一段1的數(shù)組沒(méi)有逆序?qū)Γ欢蝀X個(gè)1之后接著一段YY個(gè)0的數(shù)組有XYXY個(gè)逆序?qū)Α?br /> Farmer John偶然看見(jiàn)了這一棋盤，他好奇于可以使得游戲看起來(lái)成為平局所需要交換相鄰元素的最小次數(shù)。請(qǐng)幫助Farmer John求出這個(gè)問(wèn)題的答案。

輸入格式（文件名：balance.in）：

輸入的第一行包含NN，第二行包含2N2N個(gè)為0或1的整數(shù)。

輸出格式（文件名：balance.out）：

輸出使得游戲成為平局最少需要的移動(dòng)次數(shù)。

輸入樣例：
5
0 0 0 1 0 1 0 0 0 1

輸出樣例：
1

在這個(gè)例子中，初始時(shí)前一半有11個(gè)逆序?qū)?，后一半?3個(gè)逆序?qū)?。交換了第55和第66個(gè)數(shù)之后，兩個(gè)子數(shù)組均有00個(gè)逆序?qū)Α?br /> 供題：Dhruv Rohatgi

以上就是關(guān)于【USACO 2019 US Open Contest, Gold Problem 3. Balancing Inversions】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

【十問(wèn)十答】別盲目刷競(jìng)賽！10 個(gè)核心問(wèn)答，理清國(guó)際賽事規(guī)劃底層邏輯！