※ 引述《sophialiege ()》之銘言：
: 令[u,v]是正解
: 就是最佳解的最低處高度是u,v是最高處
: 因為每個格子的值在0~99之間,所以u和v也是在這之間
: 對於每一組假設的[u,v],你可以在圖上將高度介於這之間的位置做記號
: 看連通的記號足不足夠蓋一個部落
: 再來是要降複雜度,假如[u,v]足夠蓋,那麼[u,v+k] (k 是正整數)
: 也一定足夠 ==> bisch is possible
: 故複雜度粗估是 Constant * 100 * 8 * 40 * 40
: ^^^ ^^^ ^^^^^^^
: u log(v) graph search
我想到了一個有趣的方法
因為u和v相差越小越好, 於是可以這麼做:
令u和v一開始為0
若是[u,v]小於給定值, 便將v加上一, 讓連通的地方增加
若是[u,v]大於給定值, 則讓u加上一, 讓連通的地方減少
當u v兩人害羞的追來追去的時候, 紀錄所有符合條件的[u,v], 最後印出最小的v-u即可
這樣是對的嗎? :p
--
Edit: 已經驗證結果確實是正確的 :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.122.26.149
※ 編輯: DJWS 來自: 140.122.26.149 (09/10 22:03)