LeetCode 2561: Rearranging Fruits ·

基本資料
#

難易度: hard 第一次嘗試：2026-09-15

提交紀錄：Wrong Answer → Accepted ×2

解題思路
#

可不可能：兩籃最後要一樣，所以每種值的總數要是偶數，每籃各一半。有一種是奇數就回傳 -1。
要換哪些：每種值在籃子 1 裡多出或少了 |count1 - total / 2| 個。把兩邊多出來的都列出來（need），長度是 2 × 交換次數，每次交換把一邊多的一個和另一邊多的一個對調。
怎麼配最便宜：一次交換的成本是兩者較小的值。把 need 排序，讓便宜的前一半各配一個貴的，每次付便宜那個的值。
借最小值當中介：全域最小的水果 m 可以來回換兩次，把一對對調，成本 2m。所以每次的成本是 min(need[i], 2m)。

這是 Greedy 模板四的配對想法。

我的嘗試
#

第一版想用兩個 deque 從兩邊配對，但抵銷共同部分的 while 條件用的是 for k, v in ...items() 取出的 v，v 在迴圈裡不會變，所以會一直減到另一邊歸零，計數變成負的。例如 basket1 = [3, 3, 1]、basket2 = [1, 1, 1]：答案是 1（拿一個 3 換一個 1），這版把 1 的計數減成 -2，最後回傳 0。這版也沒有考慮用最小值當中介。

改成上面的做法，就 AC 了。

正確解法
#

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        c1, total = Counter(basket1), Counter(basket1) + Counter(basket2)
        need = []
        for v, c in total.items():
            if c % 2:
                return -1
            need += [v] * abs(c // 2 - c1[v])
        need.sort()
        m = min(total)
        return sum(min(x, 2 * m) for x in need[:len(need) // 2])