# 2499. Minimum Total Cost to Make Arrays Unequal
###### tags: `Leetcode` `Hard` `Greedy`
Link: https://leetcode.com/problems/minimum-total-cost-to-make-arrays-unequal/description/
## 思路
思路参考[这里](https://github.com/wisdompeak/LeetCode/tree/master/Greedy/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). 还有一个问题是如果出现(2,2),(3,3),(5,5)的情况，势必有一个element要被交换两次，为什么我们还是可以用ret当答案，因为只要让index0的数字被交换两次就可以了

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

a!=b，否则这是一个same pair，已经在“内部调整”时用过了。
a!=2且b!=2，否则交换之后仍然会有一个(2,2)。
满足上述两个条件，那么我们就再做一次(a,b)与(2,2)的交换即可。以此类推不断寻找下一个合适的distinct pair，直至将多余的(2,2)消耗掉。
## Code

class Solution {
    public long minimumTotalCost(int[] nums1, int[] nums2) {
        long ans = 0;
        int n = nums1.length;
        Map<Integer, Integer> map = new HashMap<>();
        int maxFreq = 0, maxFreqNum = -1, badPos = 0;
        for(int i=0; i<n; i++){
            if(nums1[i]==nums2[i]){
                map.put(nums1[i], map.getOrDefault(nums1[i], 0)+1);
                if(map.get(nums1[i])>maxFreq){
                    maxFreq = map.get(nums1[i]);
                    maxFreqNum = nums1[i];
                }
                badPos++;
                ans += i;
            }
        }
        for(int i=0; i<n; i++){
            if(maxFreq>badPos/2 && nums1[i]!=nums2[i] && nums1[i]!=maxFreqNum && nums2[i]!=maxFreqNum){
                badPos++;
                ans += i;
            }
        }
        if(maxFreq>badPos/2) return -1;
        return ans;
    }
}