一. 题目描述

{:width=”500px”}

二. 算法

哈希表

三. 分析

这道题有这么几个性质:

(1) 两个篮子加起来, 如果任意一种水果的总数为奇数, 则无解, 因为无法平分, 继而数组无法分配至一样

(2) 一个篮子里缺少的水果数量正是另一个篮子里多出的水果数量, 这里多出和缺少是相较于分配至一样后的数量

(3) 由(2)可以得到一个篮子里缺少的水果数量和多出的水果数量相等

(4) 最重要的一点, 当我们交换两个水果时, 可以直接交换, 也可以利用中介:

即假如篮子a里面多出99这个水果, 篮子b里面缺少100这个水果, 并且篮子a中还有一个水果代价为10;
则我们可以先交换篮子a的10与篮子b的100, 此时10就到了篮子b里, 再交换篮子b的10与篮子a的99;
这样我们需要花费的代价就只要10 * 2, 即20, 这比直接交换篮子a的99与篮子b的100要更优

四. 时间复杂度

$O(n)$

五. C++ 代码

typedef long long LL;

class Solution {
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {

        unordered_map<int, int> maps, num;  
        // maps存篮子1和篮子2中各类水果的代价和总数量, num存篮子1里多出或缺少的水果的代价和数量

        LL Min = 1e9 * 2;  // Min存两个篮子里最小代价的水果的两倍代价, 间接交换利用中介, 代价为Min * 2

        for(int e : basket1)
        {
            maps[e] ++ ;
            num[e] ++ ;
            Min = min(Min, (LL)e * 2);
        }
        for(int e : basket2)
        {
            maps[e] ++ ;
            Min = min(Min, (LL)e * 2);
        }

        vector<LL> arr;  // arr存篮子1多出或缺少水果的代价
        for(auto [k, v] : maps)
        {
            if(v & 1) return -1;  // 当某种水果的总量为奇数时, 无解

            if(num[k] != v / 2)
            for(int i = abs(num[k] - v / 2); i > 0; i -- ) arr.push_back(k);
        }

        // arr可以看成存的是篮子1与篮子2多出的水果的代价, 并且二者数量相等, 
        // 则我们交换的时候就应该用其中较小的来与较大的交换, 
        // 因此我们将arr从小到大排序, 而前面的一半就是直接交换的的代价,
        // 最后就是比较直接交换 与间接交换, 选取较小的代价.
        if(!arr.size()) return 0;
        sort(arr.begin(), arr.end());
        LL ans = 0;
        for(int i = 0; i < arr.size() / 2; i ++ )
        ans += min(arr[i], Min);

        return ans;
    }
};