题解 P5426 【[USACO19OPEN]Balancing Inversions】

· · 题解

题目链接

题意

给定1个长度为2n的01数组。你可以交换相邻的元素。询问最少交换次数，使得前n个元素组成的子数组中的逆序对个数等于后n个元素组成的子数组中的逆序对个数。1 \leq n\leq 10^5

题解

普通的数组中，数的种类繁多，逆序对的求解及动态维护是很复杂的情况。

考虑利用01数组的性质，探寻逆序对个数的本质。

对于1个长度为n的子数组而言，它的逆序对个数的计算方法为，对于每个1，累加其后0的个数。而该0的个数又只与该1的下标、其后1的个数有关。

不妨采用数学方法进行化简。

设长度为n的数组中，所有1出现的位置为a_i，总共有x个1。

则逆序对总数为n-a_1-(x-1) + n-a_2-(x-2) + ...+n-an-(x-x) = xn - \frac{x(x-1)}{2}-\sum_{i=1}^xa_i

应用到两个子数组逆序对个数相等的情况，则xn - \frac{x(x-1)}{2}-\sum_{i=1}^xa_i = yn - \frac{y(y-1)}{2}-\sum_{i=1}^yb_i

进一步化简，可得\frac{\sum a_i-\sum b_i}{y-x}=k，其中常数k=\frac{x+y-1-2n}{2}

因此，只要我们确定了x与y的大小，即可确定目标的左右坐标和差；也可以确定左右2个子数组各自坐标和的变化范围（全部最靠左/全部最靠右）；因此容易判断目标是否可能实现。

不妨枚举x，则y易求。在求解该情况下达成目标的最小交换次数。

交换情况看似复杂，不妨分步思考。

首先，进行必要的交换，使得左数组中有x个1，右数组中有y个1。

设move = x - lefNum，即新的左数组中1的个数与原1的个数的差值，move > 0表示应将move个1从右数组中过渡到左数组；move <0则表示应将-move个1从左数组中转移到右数组。下文仅讨论move>0的情况，move < 0也是同理。

过渡的途径唯一：交换第n与第n+1位。因此，只有它们分别为0 1时，1次交换才有意义，能达成过渡的目的。

如果要继续过渡，则应将第n位的1向左交换。综合move个元素进行过渡的情况，发现本质是：左边数组末尾空出move个0，右边数组将move个1集中到最左端，再将它们顺次过渡。

如何以最少的步数空出move个0？经过数学推导，只需找到从右往左的第move个0的位置，将原本该位置以后的1从该位开始顺次排列。步数即为这些1的目标位置和与原位置和的差值。通过简单的预处理可以快速求解。

如何以最少的步数将move个1集中到最左端？同理，找到第move个1的位置，原位置和减去目标位置和即可。

再者，要以最少的位置实现目标的坐标和差。

不难想到，任何1个子数组的坐标和要改变1，只需将某个与0相邻的1交换1次。因此其坐标和变化范围内的任何1个值都可以达到，且每改变1只需交换1次。因此，计算将元素成功过渡后的坐标和差，将其与目标的坐标和差的差值累加入本次答案中。

时间复杂度：O(n)。代码见此

回顾与思考

问题较为奇怪烦琐时，不妨利用其性质简化问题，探寻其性质。

在面对复杂问题时要有分步思考的意识和耐心，才能抵达真理的彼岸。