Readme

2499.minimum-total-cost-to-make-arrays-unequal

首先我们考虑答案至少是多少？如果所有的same pairs能够在“内部调整”后满足要求，即交换只涉及same pairs所在的位置，那么答案就是这些same pairs的下标之和。显然，这个答案是最小的，记做ret。

那么什么情况下我们能够保证所有的same pairs在“内部调整”后就能满足要求呢？只要其中的majority element不超过same pairs的总数的一半即可。举个例子(2,2),(2,2),(2,2),(1,1),(3,3),(4,4),我们只要把2和非2元素交换，就可以满足同一个pair里的两个元素不同。但是如果有过半数的majority element，例如(2,2),(2,2),(2,2),(2,2),(1,1),(3,3),那么我们就无法找到足够多的非2元素来拆散(2,2).

对于上述的第一种情况，输出ret即可。对于第二种情况，我们就需要借助于其他pair的帮助。在这个例子中，“内部调整”后我们还有两对(2,2)没有被拆散，这就需要我们找其他distinc pairs来与之交换。显然，我们会按下标从小到大去尝试。例如我们考察(a,b)的时候，思考它是否能帮助拆散(2,2)，需要满足的条件有三个：

1. a!=b，否则这是一个same pair，已经在“内部调整”时用过了。
2. a!=2且b!=2，否则交换之后仍然会有一个(2,2)。

满足上述两个条件，那么我们就再做一次(a,b)与(2,2)的交换即可。以此类推不断寻找下一个合适的distinct pair，直至将多余的(2,2)消耗掉。