给一个数组,求通过两两交换后排序这个数组, 交换有代价, 代价是交换的两个元素之和, 求排序的最小代价. 这个题我第一眼看是dp的问题, 但是很难考虑边界的元素交换, 而且很容易超时. 后来看了看答案, 原来是群论的置换群问题, 后来补了补. 发现也不是置换群, 只是单纯的置换中的轮换的概念, 关键是从哪个角度看待问题的本质(排序). 首先看置换群的概念在这里的应用, 拿例题举例: 由例子可以得知, 上面的例子最好的解法是: 取最小的数字作为媒介与其他数字做交换, 得到的成本是最小的. 然而这并不是唯一的最优解, 考虑一下的例子: 这个例子中, 可以把一个数组写成两个三阶置换, 那么对与[1,3,2],交换最小的成本并不是1与其他两个数的交换, 而是把0(全数组中最小的数字)先和1(当前数组最小数字)交换, 然后再次交换.这个最优解我没有想到 下面是如何计算最优解一: 最优解二: 答案在两个最优解中选最小的成本. 最后还有个技巧, 就是如何找到一个数组的index在排序后的对应index, 这里要用counting sort, 在counting sort中取count和的时候, 可以找到index的位置.