一个有趣的应用 -- 特征函数在确定『混乱度』算法中的应用

引言

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

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

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

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

问题

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

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

给定一个有限长度的数列$a[n]$,其中$n\in [0,n-1]$,定义混乱度为下标$i$的个数,$i$满足$a[i]=a[i+1]$;定义可执行的操作为交换任意数对$a[i]$和$a[n-1-i]$的值,试给定一种交换方法使得数列混乱度最低,并且给出最低混乱度.

想法

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