3 - 童話故事

bac

題目敘述補充
乍看之下滿難的
但
題目沒告訴你的性質是
錢可以集中成一堆或拆成多堆
不一定要一路從一個城市送到另一個城市


好
有這個性質要幹嘛呢?


先不給想弄清楚題意的人破梗
.
.
.
.
.
.
.
.
.


.


.
好~
題解
看看限制大小
時間複雜度如果到O(N^2)大概就危險了


目標是要求「最大值」


直接套看看各種常用技巧~
暴力 == 找死
DP ... 沒頭緒，看起來一點關連性都沒有
Greedy ... ... 想不到先擺著
2分搜 ... 看看能不能快速判斷某個值是否可行，啊!!!!!!! (如果不知道2分搜求最佳解在幹麼的往下看不是很詳盡的詳解)


判斷某個結果K能不能達成只需要
把>K的都送到首都
再看看夠不夠分送到 <K 的城市

結果是O(N) (N=城市數量)

再乘上2分搜的 Log(M)  (M = 最大可能 - 最小可能)

結果是~~~
O(N*Log(M))

完成~~~




/* 2分搜求最佳解 */
當我們知道解答是這樣的情況

就像在排序好的數列裡進行2分搜尋一樣(一邊 <=  另一邊 > 之類的)

我們可以用 "嘗試該值是否為可行解" 當做判斷條件來2分搜
所以囉~ 自己手暴一個2分搜尋在競賽也是重要技能~

類似題：電梯向上 ( NPSC 高中組初賽)