淺談二分策略的應(yīng)用(更新版)
【正文】 元素； 如果 i=p，表示第 i小的元素就是 x ip，我們將范圍確定為 大的元素，求該范圍內(nèi)第 p1個(gè)元素； 5/19/2023 7 WinterCamp 2023 小結(jié) ?舉這個(gè)例子，是想說(shuō)明兩點(diǎn)： ? 第一，二分查找 == logn ? 第二，二分查找 == 平均 ? ?5/19/2023 8 WinterCamp 2023 類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?與類型一中的二分查找相比， 最大的區(qū)別 在于這里的二分在判斷選擇哪一個(gè)部分遞歸調(diào)用時(shí)沒(méi)有了 比較運(yùn)算 *。 K （ 1≤K≤N1） — 比賽既要講求實(shí)力，又要考慮到運(yùn)氣。 ?證明： ? 情況一： Y被 Z≠X擊敗 Z?? … Y ?? … X ?? Z? … ?? … ?? … ?? Y X X X YYYX5/19/2023 13 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 5/19/2023 17 WinterCamp 2023 類型三：二分搜索 —— 應(yīng)用于無(wú)序序列 二分策略 有序 序列 無(wú)序 序列 5/19/2023 18 WinterCamp 2023 例三：推銷員的旅行 ? [問(wèn)題轉(zhuǎn)述 ] 這是一個(gè)交互式問(wèn)題： 在一個(gè)未知的競(jìng)賽圖（即有 N頂點(diǎn)，兩點(diǎn)間恰只含一條邊的有向圖）中，通過(guò)不斷詢問(wèn)任意兩點(diǎn)之間邊的方向，尋找一條哈密爾頓路 。且已知 A1?i+1， i+1?Ai。 ?這就要求我們能有 ? 扎實(shí)的基本功 ? 豐富的解題經(jīng)驗(yàn) ? 大膽合理的猜測(cè) ? 活躍的創(chuàng)造思維 ?方可? 以不變應(yīng)萬(wàn)變 ?！ 5/19/2023 27 WinterCamp 2023 5/19/2023 28 WinterCamp 2023
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1