淺談二分策略的應用-全文預覽
【正文】 ?于是，我們可以 二分枚舉 獲勝的 X。 5/19/2023 10 WinterCamp 2023 初步分析 ?由于 N很大，猜想可以通過貪心方法解決。每頭奶牛都有一個 BTP排名，恰為 1－ N。 如果 ip，我們將范圍確定為 S中比 x小的元素，求該范圍內(nèi)第 i個元素； 如果 i=p，表示第 i小的元素就是 x ip，我們將范圍確定為 大的元素，求該范圍內(nèi)第 p1個元素； 5/19/2023 7 WinterCamp 2023 小結 ?舉這個例子，是想說明兩點： ? 第一，二分查找 == logn ? 第二，二分查找 == 平均 ? ?5/19/2023 8 WinterCamp 2023 類型二：二分枚舉 —— 應用于退化了的有序序列 ?與類型一中的二分查找相比， 最大的區(qū)別 在于這里的二分在判斷選擇哪一個部分遞歸調(diào)用時沒有了 比較運算 *。例如： S={ 3, 7, 2, 6, 8, 1, 5 }， i=4 Answer=5 5/19/2023 6 WinterCamp 2023 問題的一般解法 ? 二分查找的過程： （ 1）確定待查找元素在 S中 （ 2）在 n個元素中 隨機 取出一個記為 x，將 x作基準 （ 3）設 S中比元素 x小的有 p個 （ 4）如果找出 x，輸出；否則轉至（ 2） ? 因為 x是 隨機選出 的，由簡單的概率分析，可得算法的復雜度期望值為 O(n)。 K （ 1≤K≤N1） — 比賽既要講求實力，又要考慮到運氣。并要求你列舉出一個可能的比賽安排使該奶牛獲勝。 ?證明： ? 情況一： Y被 Z≠X擊敗 Z?? … Y ?? … X ?? Z? … ?? … ?? … ?? Y X X X YYYX5/19/2023 13 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手
教學課件相關推薦
鄂ICP備17016276號-1