淺談二分策略的應(yīng)用(留存版)
【正文】 023 初步分析 ?為了避免詢問的盲目性，我們嘗試使用 增量法 逐步擴(kuò)展序列。我們不能讓二分思想僅僅停留在一般有序數(shù)組上的最基本的二分查找，而應(yīng)該擴(kuò)展到更廣泛的應(yīng)用上。 ?所以，今后我們?cè)诳紤]最優(yōu)性問題時(shí)，應(yīng)當(dāng)注意問題是否 隱含 了一個(gè)有序的 01序列，它是否可以用二分枚舉將 最優(yōu)性問題 轉(zhuǎn)化為 可行性問題 。 顯式 有序序列 隱含的退化了的 有序序列 5/19/2023 9 WinterCamp 2023 例二： BTP職業(yè)網(wǎng)球賽 ? [問題描述 ] N（ N≤65536） — 有 N頭奶牛（ N是 2P）參加網(wǎng)球淘汰賽。 ?解決方法： 枚舉！ 3?1 4?2 7?5 8?6 4?3 8?7 4?8 圖 BTP1 6?7 5?3 4?8 2?1 6?5 4?2 6?4 圖 BTP2 5/19/2023 12 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 i+1 i+1 A1 A2 A3 Ai 5/19/2023 22 WinterCamp 2023 二分搜索的使用 ? 由于 對(duì)每個(gè)點(diǎn) Ak(1≤k≤i)，要么 Ak?i+1，要么i+1?Ak。因此，我們可以用 二分搜索 來尋找 Ak，使 i+1可以插入 Ak與 Ak+1之間。 ?證明： ? 情況二： Y被 X擊敗 Y?? … X ?? … ? … … ?? … ?? X X Y X YYY X5/19/2023 14 WinterCamp 2023 問題的解決 ?于是，我們可以 二分枚舉 獲勝的 X。例如： S={ 3, 7, 2, 6, 8, 1, 5 }， i=4 Answer=5 5/19/2023 6 WinterCamp 2023 問題的一般解法 ? 二分查找的過程：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1