相关链接：http://oeis.org/A036604

题目大概的意思是问你任意n个数，将这n个数排好序的最少比较次数，比如n = 5的时候，次数就为7。

(可以比较数列中的任意两个数，而不是必须相邻的两个才可交换）

读了一本叫做《啊哈！算法》的书的第九章：还能更好吗---微软亚洲研究院面试。感觉绝对众数问题的确有趣，可以通过反证的思维方式解决这类问题。也许就像知乎上的一个话题关于人类的大脑有哪些天生的设计缺陷中我们大脑所习惯的运作方式其实不大支持严格的逻辑判断是导致大多数人第一次看到这类问题无法快速解决的原因。

比如请问以下的两个选项哪个选项更可能成立。 已知S君非常喜欢画画,

A. S君喜欢游泳 B. S君有许多绘画方面的朋友并且喜欢游泳。

显然A是正确的，但大多数人选的却是B，这也说明了人类大脑并不大支持严格的逻辑判断。

好，言归正传。如何解决这个绝对众数问题呢？题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2456

最简单的方法应该是用个双重循环，时间复杂度为$O(n^2)$，相信这样的算法绝大多数人都能想到。既然是最简单的算法，往往也不是最优秀的算法。

那有没有更快更好的方法呢？显然是有的。 第二种方法是将数组排个序，当然数组的下标从0开始，那么$n/2$的位置显然是绝对众数。听到这，也许有人不能一下子理解为什么下标为$n/2$所代表的数显然是绝对众数，是这样的：比如有n个数字，假设n是偶数且等于10，那么就有$10/2+1=6$个绝对众数，因为说了有一个数出现的次数超过50%。可以假设两种极端情况，一种是绝对众数都最靠数组的左边(即下标0)，一种最靠右，一个长度为10的数组中6个连续的数最靠左或者最靠右会发现这两种情况都满足数组下标$n/2$所代表的数是绝对众数，这其实很显然，也就是说如果这6个连续的数不在最左不在最右唯一的可能就是绝对众数们更加靠近下标$n/2$，奇数同理。

由于排序算法的时间复杂度可以做到$O(nlogn)$，绝对众数问题到此为止也可以做到$O(nlogn)$。

那有没有线性的算法呢？考虑到无法做到比线性算法更优因为仅读入n个数字的时间复杂度也已经是线性的。

第一种容易想到的线性做法类似于桶排序，但如果数的空间跨度很大比如1，10000，10000000怎么办？很简单离散化一下即可，用C++中的unordered_map很容易实现。

第二种方法相信聪明的读者在前面已经考虑到排序真正的目的究竟是为了使数连续还是让数按照顺序排列，可以说更多的显然是使数连续，为什么这么说呢？因为即便数组里的数字大小并无顺序但只要数字是连续的就可以做到数组中第$n/2$位置是绝对众数。

但是否也可以通过求第$n/2$大的数来求出正确答案呢，显然可以，没错，第$n/2$大的数就是绝对众数。为什么这么说？ 因为排序后位置处于最中间的数一定是绝对众数那绝对众数也一定是排序后在最中间的数，两者等价。确定的有BFPRT算法可以在严格线性的时间复杂度内解决问题。

最后一种是我见过的最妙的解法，可以说比前面所有的方法都显得贴近本质，也只有这种方法可以解决bzoj 2456（除非你通过java等语言钻空子)，即考虑到一定有数的出现次数超过50%，那么即便是所有的绝对众数和非绝对众数一一抵消了最后留下来的仍然会是一个绝对众数，所以最后剩下的数一定是绝对众数。这种解法连数组都不用，几个变量即可。

所以解决这类问题可以用类似于"为什么一个人投票数超过50%这人就直接当选？ 因为剩下的投票数不可能超过50%，如果超过50%，总量就超过了100%，那显然是不成立的"这种反证的思维方式。

备注：众数（mode）指一组数据中出现次数最多的数据值。例如{2,3,3,3}中，出现最多的是3，因此众数是3，众数可能是一个数，但也可能是多个数。数学里并没有绝对众数这种说法，在此，绝对众数的定义见bzoj 2456。

原题链接： https://www.luogu.org/problem/show?pid=1031

仅将原题题面中的"移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。"，改为："移牌规则为：可以将任意的纸牌个数移到任意编号的堆上"。

对于改动后的问题，存不存在时间复杂度在多项式以内的解法？