Java教程

# $\texttt{Sol. Luogu P6186}$ [NOI online #1 提高] 冒泡排序

本文主要是介绍# $\texttt{Sol. Luogu P6186}$ [NOI online #1 提高] 冒泡排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

\(\texttt{Sol. Luogu P6186}\) [NOI online #1 提高] 冒泡排序

太毒瘤啦!!!果然是我太菜(水)了......

题目描述

给定一个 \(1 ∼ n\) 的排列 \(p_i\),接下来有 \(m\) 次操作,操作共两种:

  1. 交换操作:给定 \(x\),将当前排列中的第 \(x\) 个数与第 \(x+1\) 个数交换位置。
  2. 询问操作:给定 \(k\),请你求出当前排列经过 \(k\) 轮冒泡排序后的逆序对个数。
    对一个长度为 \(n\) 的排列 \(p_i\) 进行一轮冒泡排序的伪代码如下:
for i = 1 to n-1:
  if p[i] > p[i + 1]:
    swap(p[i], p[i + 1])

思路:

很显然,我们必须先思考有关冒泡排序的本质,获得相关性质,才能继续做题。

所以这个本质是什么呢?

干想了一会,啥也没想出来,就举个例子:

\(\text{4 3 5 2 1}\to\text{3 4 2 1 5}\)

大概能发现,一个数能往后交换,仅当它左边已经没有了比他大的数。这样,它才能往后交换,去“消灭”逆序对。开始时,一个数的前面有多少个大于它的数,它就要交换多少次,本轮就不能发挥它的作用。当前轮有 \(x\) 个能交换的数,就有 \(n-x\) 个逆序对被消灭。一个数的前面有 \(t\) 个比他大的数,这个数在 \(t+1\) 轮排序才会往后交换。

我们要求的,是冒泡排序进行 \(k\) 轮后逆序对的个数,那就把不修改的情况预处理出来,再考虑修改对答案带来的影响。

记 \(a[i]\) 为原数列, \(b[i]\) 为 \(a[i]\) 前面有多少个数比他大。将 \(\{b\}\) 丢进一个桶里(\(h\)),在这个桶上建立树状数组求前缀(因为对于\(b\)中的非零数来说每轮被交换一次,每轮是要\(-1\)的,故当前 \(b\) 中 \(0\) 的个数再拿 \(n\) 减就是本轮逆序对减少的数量,所以是求前缀)就可以预处理出第 \(i\) 轮减少的逆序对个数。

然后就是考虑修改带来的影响。

容易发现,相邻的两项交换,对整体逆序对个数的影响只能是 \(+1(a_x<a_{x+1})\) 或 \(-1(a_x>a_{x+1})\) 。以 \(+1\) 为例,这个变换在序列 \(\{b\}\) 中的影响就是 \(b_{x+1}+1\) 。在 \(b_{x+1}\) 这一项 \(+1\) 后,即 \(b_{x+1}\) 执行冒泡后,剩余部分和未交换的结果就是一样的了。

$$\left[\begin{matrix}a:&4&3&5&2&1\ b:&0&1&0&3&4\ h:&2&1&0&1&1\end{matrix}\right]\ \overset{\text{Exchanging a[2]&a[3]}}{\longrightarrow} \ \ \left[\begin{matrix}a:&4&5&3&2&1\ b:&0&0&2&3&4\ h:&2&0&1&1&1\end{matrix}\right]$$

根据“当前轮有 \(x\) 个能交换的数,就有 \(n-x\) 个逆序对被消灭”这句话,我们用 \(n(=5)\) 依次减 \(\{h\}\) 的前缀和,得到每轮减少的逆序对个数:

原来:\([2,1,0,1,1]\to[3,2,2,1,0]\)

之后:\([2,0,1,1,1]\to[3,3,2,1,0]\)

对这个新得出来的序列再做前缀和。容易发现,做完前缀和后交换操作可以很方便维护。当然,因为我们要的是 \(k\) 趟冒泡排序后的结果,所以这个答案序列是要不断单点更新 + 求前缀和的,用树状数组维护。

(大概是对的吧...?)代码明天写。

为什么想不出来?\(\huge\text{思维浅了!}\) 或者是 \(\huge\text{模拟能力不够?}\)

这篇关于# $\texttt{Sol. Luogu P6186}$ [NOI online #1 提高] 冒泡排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!