淺談二分策略的應用(專業(yè)版)
【正文】 且已知 A1?i+1， i+1?Ai。 ?證明： ? 情況一： Y被 Z≠X擊敗 Z?? … Y ?? … X ?? Z? … ?? … ?? … ?? Y X X X YYYX5/19/2023 13 WinterCamp 2023 性質：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 如果 ip，我們將范圍確定為 S中比 x小的元素，求該范圍內第 i個元素； 如果 i=p，表示第 i小的元素就是 x ip，我們將范圍確定為 大的元素，求該范圍內第 p1個元素； 5/19/2023 7 WinterCamp 2023 小結 ?舉這個例子，是想說明兩點： ? 第一，二分查找 == logn ? 第二，二分查找 == 平均 ? ?5/19/2023 8 WinterCamp 2023 類型二：二分枚舉 —— 應用于退化了的有序序列 ?與類型一中的二分查找相比， 最大的區(qū)別 在于這里的二分在判斷選擇哪一個部分遞歸調用時沒有了 比較運算 *。 1 5/19/2023 16 WinterCamp 2023 小結 ?應用這類二分枚舉的 最優(yōu)性問題 近來很是熱門（如 NOI2023樹的劃分），而且這類試題很容易誘導選手 直接 采用 動態(tài)規(guī)劃 或是 貪心算法，而走入死胡同。 ?這里我想指出的是：二分思想雖然簡單，但是它的內容還是非常豐富的。 ?我們先任意詢問兩個點 ?不妨設詢問結果是 1到 2有邊，于是，我們就得到一條長度為 1的線路。 Answer— 現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。如果兩頭奶牛的排名相差大于給定整數(shù) K，則排名靠前的奶?？偸勤A排名靠后的奶牛；否則，雙方都有可能獲勝。 思考 . . . 5/19/2023 19 WinterCamp 2
教學課件相關推薦
鄂ICP備17016276號-1