重排水果

题目

6345. 重排水果

---

你有两个果篮，每个果篮中有 n 个水果。给你两个下标从 0 开始的整数数组 basket1 和 basket2 ，用以表示两个果篮中每个水果的成本。

你希望两个果篮相等。为此，可以根据需要多次执行下述操作：

• 选中两个下标 i 和 j ，并交换 basket1 中的第 i 个水果和 basket2 中的第 j 个水果。
• 交换的成本是 min(basket1i,basket2j) 。

根据果篮中水果的成本进行排序，如果排序后结果完全相同，则认为两个果篮相等。

返回使两个果篮相等的最小交换成本，如果无法使两个果篮相等，则返回 -1 。

示例 1：

输入：basket1 = [4,2,2,2], basket2 = [1,4,1,2]
输出：1
解释：交换 basket1 中下标为 1 的水果和 basket2 中下标为 0 的水果，交换的成本为 1 。此时，basket1 = [4,1,2,2] 且 basket2 = [2,4,1,2] 。重排两个数组，发现二者相等。

示例 2：

输入：basket1 = [2,3,4,1], basket2 = [3,2,5,1]
输出：-1
解释：可以证明无法使两个果篮相等。

提示：

• basket1.length == bakste2.length
• 1 <= basket1.length <= 10^5
• 1 <= basket1i,basket2i <= 10^9

题解

方法一：

思路

首先两个数组中出现的所有数的次数都是偶数次，否则没有答案，输出-1。

求出两个数组中的最小值mn。

然后将basket1中多出的数存到c1；将basket2中多出的数存到c2。
两者的个数都会相等。

将c1升序排序，c2降序排序。

每次让c1[i]和c2[i]交换，需要的代价是min(c1[i], c2[i])，我们还可以让最小的元素mn参与交换，不妨设mn在c1中，那么mn先与c2[i]交换，然后再与c1[i]交换，需要代价为2*mn，因此对于c1[i]和c2[i]的交换最小代价为min(c1[i], c2[i], 2*mn)

代码

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        long long mn = min(*min_element(basket1.begin(), basket1.end()), *min_element(basket2.begin(), basket2.end()));
        map<int,int> mp, mp1, mp2;
        for (int i:basket1) mp[i]++, mp1[i]++;
        for (int i:basket2) mp[i]++, mp2[i]++;
        for (auto& [i,j]:mp) {
            if (j%2) return -1;
            j/=2;
        }
        vector<long long> c1, c2;
        for (auto& [i,j]:mp1) {
            if (mp[i]<j) {
                for (int sz=j-mp[i], k=0; k<sz; k++) {
                    c1.push_back(i);
                }
            }
        }
        for (auto& [i,j]:mp2) {
            if (mp[i]<j) {
                for (int sz=j-mp[i], k=0; k<sz; k++) {
                    c2.push_back(i);
                }
            }
        }
        // for (int i:c1) cout << i << " "; cout << endl;
        // for (int i:c2) cout << i << " "; cout << endl;
        long long sz = c1.size(), ans = 0;
        reverse(c2.begin(), c2.end());
        for (int i=0; i<sz; i++) {
            ans += min({c1[i], c2[i], 2*mn});
        }
        return ans;
    }
};