Re: [閒聊] 每日leetcode
直覺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
至於答案那個最精簡的全部一起排序的方法
我白癡想不到
我超爛
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754118532.A.CB6.html
推
08/02 15:13,
4月前
, 1F
08/02 15:13, 1F
推
08/02 15:17,
4月前
, 2F
08/02 15:17, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1488 之 1548 篇)：