引言

本篇将记录我对一道算法题的一些思考,用到了特征这一概念进行解答,以及特征的具体构造式实际上是由圆法所启发的.

但是实际上也只要求提供一种有效的算法而已,因此构造式并没有发挥出作用来,只需要利用到特征函数这一概念就能比较好的说明思路了(可能其他人看来还是会一头雾水,一下子蹦出这么多符号来).

或许利用具体的构造式,可能就通过对的分析,便能得到混乱度上下界的一个估计(应该吧,我也不确定hhh).但是由于的不确定性,我也没有什么好的手段进一步探究特征函数的作用.

这里说明一下:这些内容我并没有详细参考资料,纯粹是记录一下自己的一个idea在具体问题下的使用.因此可以说,肯定是不严谨的,一些想法可能还是错误的,不要太认真即可.

问题

题目来源可见原题链接,下面给出题目图片:

然后是『著名算法大师』Paitsai对该问题的简单翻译:

给定一个有限长度的数列,其中,定义混乱度为下标的个数,满足;定义可执行的操作为交换任意数对和的值,试给定一种交换方法使得数列混乱度最低,并且给出最低混乱度.

想法

以下是我对该问题在理论上的考虑方式: