# Leetcode 2499. Minimum Total Cost to Make Arrays Unequal
###### tags: `leetcode` `殘酷daily` `Greedy` `hash_map`

[題目連結](https://leetcode.com/problems/minimum-total-cost-to-make-arrays-unequal/)

# Method Hash map
:::info
:bulb: **作法講解**:
## Concept
* If maximum count of same value is bigger than total size divided by 2,
=> we can not make arrays unequal.

* If maximum count of same value is less and equal than duplicate size divided by 2.
=> we only need change the elements with same value.

* If maximum count of same value is bigger than duplicate size divided by 2.
we need use the elements with different value.
=> the cost of smaller index is cheap than larger index.

## Initialize
set "max_cnt" is 0, using "max_cnt" to record maximum frequency of same value.

set "max_cnt_val" is 0, using "max_cnt_val" to record the value with maximum frequency of same value.

set "dup_cnt" is 0, using "dup_cnt" to record total count of same value.

set "output" is 0, using "output" to record the cost.

## Flow
1. we can scan each element from start to end
if "nums1[i]" is equal with "nums2[i]"
then do following step

**a. increase the frequency of nums1[i]**
**b. increase "dup_cnt"**
**c. record "max_cnt" and "max_cnt_val"**
**d. compute "output" plus by i**

2. compute "res" by 2 * "max_cnt" minus "dup_cnt"

3. we can scan each element from start to end
when "res" is bigger than 0, and "nums1[i]" is different "nums2[i]"
and "nums1[i]" is different "max_cnt_val"
and "nums2[i]" is different "max_cnt_val"
than do following step

**a. decrease "res"**
**b. compute "output" plus by i**
:::

TC: O(N) SC: O(N)
完整程式碼

class Solution {
public:
    typedef long long ll;
    long long minimumTotalCost(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        int max_cnt = 0;
        int dup_cnt = 0;
        ll output = 0;
        unordered_map<int, int> m;
        int max_cnt_val = 0;
        int res = 0;

        for(int i = 0 ; i < n ; i++) {
            if(nums1[i] == nums2[i]) {
                m[nums1[i]]++;
                if(m[nums1[i]] > max_cnt) {
                    max_cnt = m[nums1[i]];
                    max_cnt_val = nums1[i];
                }
                dup_cnt++;
                output += i;
            }
        }

        res = max_cnt - (dup_cnt - max_cnt);
        for(int i = 0 ; (i < n) && (res > 0) ; i++) {
            if((nums1[i] != nums2[i])&& (nums1[i] != max_cnt_val) && (nums2[i] != max_cnt_val)) {
                res--;
                output += i;
            }
        }
        return (res <= 0) ? output : -1;
    }
};

:::