NOI2018 冒泡排序规律证明

约定不等于承诺〃 2021-11-17 21:56 340阅读 0赞

其实网上对于找到规律之后的部分已经讲的很详细了，在这里只较为严谨的证明一遍这个规律（毕竟网上不少人都说"打表可得"）。

首先，我们考虑，对于排列中的一个数i，它对于逆序对的贡献的下界一定是|i-pi|。（这里认为逆序对是有序数对）

假如pi<i，那么就算它前面的都比它小，那么也至少有i-pi个数在它面前但是比他小，而其他的情况都不会比这种情况少。pi>i的情况类似。

我们设在pi<i时，对于i，在他前面有k个数比i大。

那么，i对逆序对的贡献就是**k+(n-pi)-(n-i-k)=i-pi+2k**。

这个式子中的k是前面比它大的数和它形成的逆序对；(n-pi)是在i前面的数的个数；(n-i-k)的意思是在i之后比i大的数，因为比i大的数一共有n-i个，在i前面有k个，故在i后面有n-i-k个；(n-pi)-(n-i-k)一起表示在i之后的比i小的数。

而对于pi>i时，设在i之后且小于i的数有k个，用同样的方法可以推出i对逆序对的贡献就是k+(n-pi)-(n-i-k)=pi-i+2k。

综上，一个排列中的任意一个数i对逆序对的贡献就是|i-pi|+2k。因为我们要让总的逆序对数=sigma |i-pi|，那么对于任意一个数，k都应该为零。

k为0意味着什么？

**对于一个数i，若pi<i，则它前面的数都比他小；反之，则它后面的数都比他大。（下文称此为条件1）**

然后我们来证明，条件1和“排列中不存在长度大于2的下降子序列”（下文称此为“条件2”）完全等价。

**命题1：不满足条件2的排列一定不满足条件1。**

如果一个排列中有长度大于2的下降子序列，那么对于这个下降子序列的中间的任意一个数（中间是指不在这个下降子序列的两端）一定不满足条件1。

想一想，它的前面至少有一个比它大的，后面有一个比它小的，那么，不管是i<pi还是i>pi都不满足条件1.

**命题2：满足条件2的排列一定满足条件1。**

考虑排列中的任意一个数，他可能是i>pi，也可能反过来，这里只讨论i<pi的情况。

对于i<pi,因为满足条件2，所以对于i，只可能有两种情况：1.有一个比它大的数在它前面，它后面的数都比它大；2.有一个比它小的数在它后面，它前面的数都比它小。

情况2是不存在的的，因为有一个比它大的数在它前面，而一定至少有一个比它小的数在它后面（i前面的位置不够，不能放下所有比i小的数），违背了条件1，自相矛盾。

对于情况1，他是满足条件1的。

故证毕。

转载于:https://www.cnblogs.com/thedreammaker/p/11011195.html

发表评论取消回复

表情：

评论列表（有 0 条评论，340人围观）

还没有评论，来说两句吧...

相关阅读

相关 [NOI2018]归程

[\[NOI2018\]归程][NOI2018] 这题我只会离线做法..在线做法的克鲁斯卡尔重构树我虽然会但是...我不会倍增...所以就比较困难,于是暂时先只写了离线做法

桃扇骨/ 2023年06月02日 11:57/ 0 赞/ 20 阅读

相关 @loj - 2720@ 「NOI2018」你的名字

目录 @description@ @solution@ @accepted code@ @details@ --------------------

悠悠/ 2023年06月01日 13:57/ 0 赞/ 14 阅读

相关【排序】冒泡排序

[冒泡排序][Link 1]（英语：Bubble Sort）又称为泡式排序，是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过

客官°小女子只卖身不卖艺/ 2022年12月13日 04:41/ 0 赞/ 295 阅读

相关冒泡排序原理，php冒泡排序，golang冒泡排序

要写出冒泡排序，首先要知道冒泡排序的原理，参考这篇文章：[http://c.biancheng.net/view/6506.html][http_c.biancheng.net

淩亂°似流年/ 2022年11月01日 13:46/ 0 赞/ 281 阅读

相关动态规划冒泡排序爱奇艺2018招聘

这次分析一下2018年爱奇艺招聘的冒泡排序的题目。题目描述：牛牛学习了冒泡排序,并写下以下冒泡排序的伪代码,注意牛牛排序的数组a是从下标0开始的。 BubbleS

缺乏、安全感/ 2022年03月25日 07:08/ 0 赞/ 298 阅读

相关 [NOI2018] 你的名字

\[NOI2018\] 你的名字该来的总归还是会来的…… 题意： [题目传送门][Link 1] 一句话题意：给出一个字符串\\(T\\)，\\(Q\\)组询

墨蓝/ 2021年12月14日 10:45/ 0 赞/ 279 阅读

相关 NOI2018 冒泡排序规律证明

其实网上对于找到规律之后的部分已经讲的很详细了，在这里只较为严谨的证明一遍这个规律（毕竟网上不少人都说"打表可得"）。首先，我们考虑，对于排列中的一个数i，它对于逆序对的贡

约定不等于承诺〃/ 2021年11月17日 21:56/ 0 赞/ 341 阅读

相关【洛谷4769】[NOI2018] 冒泡排序（动态规划_组合数学）

题目： [洛谷 4769][4769] 博客页面左下角的嘴嘴瓜封神之战中的题目分析：一个排列交换次数为 \\(\\frac\{1\}\{2\}\\sum\_

小鱼儿/ 2021年11月12日 00:38/ 0 赞/ 288 阅读

相关【LOJ】#2720. 「NOI2018」你的名字

题解把S串建一个后缀自动机用一个可持久化权值线段树维护每个节点的right集合是哪些节点求本质不同的子串我们就是要求T串中以每个点为结束点的串有多少在\\(S\

Myth丶恋晨/ 2021年11月01日 13:48/ 0 赞/ 332 阅读

相关【LuoguP4770】[NOI2018] 你的名字

[题目链接][Link 1] 题意简述给定一个串 \\(S\\) 多组询问 , 每次给定一个串 \\(T\\) 和一个区间 \\(\[l,r\]\\) 求串

布满荆棘的人生/ 2021年09月29日 21:42/ 0 赞/ 302 阅读