#115: 反悔貪心


211096@stu.cchs.chc.edu.tw (唐狗針)

學校 : 彰化縣精誠中學
編號 : 872
來源 : [61.223.79.98]
最後登入時間 :
2024-12-01 20:39:24
a500. 外送接單 (Delivery) | From: [61.223.111.138] | 發表日期 : 2024-10-23 22:17

看到的直覺可能是越早結束的越早做,但顯然會有反例,像是

時間  截止

5      6

6      7

4      8

5      9

最優解是選 4 8 和 5 9

但如果按照上面的貪心策略會選擇5 6然後就不能拿了

會出現這種問題是因為截止時間早的處理時間太久了

但不管做的時間多久,收益都是 1

那不如,如果兩個工作確定只能選一個,選做的時間越短越好,把時間留給後面的外送

於是我們可以把確定可以做的丟進資料結構裡,把不確定的(也就是上面說的兩個工作只能選一個),淘汰掉處理時間最久的一定更優

 

整體解法 :

按截止時間排序

掃過每個外送 有三種情況

1. 截止時間內可以處理 

2. 截止時間內不能處理 但淘汰已處理的外送中花費時間最久的單子 就能夠處理

3. 淘汰已處理的外送中花費時間最久的單子 仍然沒辦法處理

這三種情況想好怎麼做就能AC了 這題的重點在狀況 2.

 
ZeroJudge Forum