自动搬运

查看原文

来自洛谷，原作者为

	littlewyy 回归

搬运于2025-08-24 22:10:38，当前版本为作者最后更新于2019-06-29 21:31:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题意

给定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)$。代码见此

回顾与思考

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

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