竹園論壇
標題:
3 - 童話故事
[打印本頁]
作者:
bac
時間:
2014-11-8 19:08
標題:
3 - 童話故事
本帖最後由 bac 於 2014-11-8 19:17 編輯
題目敘述補充
乍看之下滿難的
但
題目沒告訴你的性質是
錢可以集中成一堆或拆成多堆
不一定要一路從一個城市送到另一個城市
好
有這個性質要幹嘛呢?
先不給想弄清楚題意的人破梗
.
.
.
.
.
.
.
.
.
.
.
好~
題解
看看限制大小
時間複雜度如果到O(N^2)大概就危險了
目標是要求「最大值」
直接套看看各種常用技巧~
暴力 == 找死
DP ... 沒頭緒,看起來一點關連性都沒有
Greedy ... ... 想不到先擺著
2分搜 ... 看看能不能快速判斷某個值是否可行,啊!!!!!!! (如果不知道2分搜求最佳解在幹麼的往下看不是很詳盡的詳解)
判斷某個結果K能不能達成只需要
把>K的都送到首都
再看看夠不夠分送到 <K 的城市
結果是O(N) (N=城市數量)
再乘上2分搜的 Log(M) (M = 最大可能 - 最小可能)
結果是~~~
O(N*Log(M))
完成~~~
/* 2分搜求最佳解 */
當我們知道解答是這樣的情況
1.png
(7.04 KB, 下載次數: 17)
下載附件
2分搜
2014-11-8 19:03 上傳
就像在排序好的數列裡進行2分搜尋一樣(一邊 <= 另一邊 > 之類的)
我們可以用 "嘗試該值是否為可行解" 當做判斷條件來2分搜
所以囉~ 自己手暴一個2分搜尋在競賽也是重要技能~
類似題:
電梯向上
( NPSC 高中組初賽)
歡迎光臨 竹園論壇 (http://forum.tfcis.org/)
Powered by Discuz! X3.2