直觉greedy是想说，用最小的去换最大的
然后就分两个pq记
pq_1记basket_1比basket_2多的数量，并用min_pq
pq_2反之，记下basket_2比较多的数量，并用max_pq
每次iter就是pq_1取最小跟pq_2取最大来换
然后算cost
不过就错了 对啊
后来看答案才知道有假交换，用最小cost那颗做两次交换，有可能比直接交换还要省
就把这个条件加进去，就对了
def minCost(self, basket1: List[int], basket2: List[int]) -> int:
a_cnt = Counter(basket1)
b_cnt = Counter(basket2)
mn = min(min(basket1), min(basket2))
a_pq = []
for k,v in a_cnt.items():
if b_cnt[k]<v: # if k not in b, b[k] will be 0
heappush(a_pq, (k, v-b_cnt[k]))
b_pq = []
for k,v in b_cnt.items():
if a_cnt[k]<v:
heappush(b_pq, (-k, v-a_cnt[k]))
cost = 0
while a_pq and b_pq:
cur_a, cur_a_cnt = heappop(a_pq)
cur_b, cur_b_cnt = heappop(b_pq)
cur_b = -cur_b
if cur_a_cnt%2==1 or cur_b_cnt%2==1:
return -1
if cur_a_cnt>cur_b_cnt:
cost += (cur_b_cnt//2)*min(cur_a, cur_b, 2*mn)
heappush(a_pq, (cur_a, cur_a_cnt-cur_b_cnt))
elif cur_b_cnt>cur_a_cnt:
cost += (cur_a_cnt//2)*min(cur_a, cur_b, 2*mn)
heappush(b_pq, (-cur_b, cur_b_cnt-cur_a_cnt))
else:
cost += (cur_a_cnt//2)*min(cur_a, cur_b, 2*mn)
return cost
至于答案那个最精简的全部一起排序的方法
我白痴想不到
我超烂