#3684: 二分搜


TobywithDino (Toby)

學校 : NTOU
編號 : 1233
來源 : [140.115.204.124]
最後登入時間 :
2023-01-08 18:18:14
a674. B. 要筷子嗎?自己做就好啦 -- 110學年度FD校內資訊學科能力競賽(二) | From: [140.115.204.124] | 發表日期 : 2023-01-08 18:47

學長教我用二分搜

我猜是因為你從1~max長度找的話會TLE

總之用二分搜 l=1 因為最短的答案就是1了 r=木棍中最長的長度 因為有可能都不用割就分好了

而筷子也不能變長,所以r就是最長的那根長度

利用二分搜尋找,每次mid都會查看有沒有符合題目需求,若有符合,則繼續往長找,也就是l = m+1

反之則r = m-1

查看mid有沒有符合題目需求則是需要檢查每根原有木棍除以mid(長度)可以切幾份,分給題目的m人(m*2根)

也就是 份數 = ai/mid 而每根都加完後,檢查份數有無滿足。

 
ZeroJudge Forum