淺談二分策略的應(yīng)用(完整版)
【正文】 3）關(guān)鍵字比較，確定更精確的范圍 （ 4）判斷結(jié)果，如不夠精確，轉(zhuǎn)至（ 2） 5/19/2023 5 WinterCamp 2023 例一：順序統(tǒng)計問題 ? [問題描述 ] 給定一個由 n個不同的數(shù)組成的集合 S，求其中第 i小的元素。 Answer— 現(xiàn)在觀眾們想知道，哪頭奶牛是所有可能成為冠軍的牛中排名最靠后的。 ?如果利用靜態(tài)排序二叉樹，整個問題可以在O(Nlog2N)時間完成。 ?我們先任意詢問兩個點 ?不妨設(shè)詢問結(jié)果是 1到 2有邊，于是，我們就得到一條長度為 1的線路。 i+1 i+1 A1 A[i/2] Ai i+1 5/19/2023 23 WinterCamp 2023 小結(jié) ?算法的根本 —— 在一個無序的 01序列中進(jìn)行二分查找 0 0 1 0 1 1 1 0 0 1 1 1 ?我們所尋找的 —— 一個特殊的子串‘ 01’ 0 1 5/19/2023 24 WinterCamp 2023 小結(jié) ?由此可見，這樣的二分搜索方法往往應(yīng)用于那些 可行解較多 ，但需要高效地 構(gòu)造一組可行解 的問題。 ?這里我想指出的是：二分思想雖然簡單，但是它的內(nèi)容還是非常豐富的。 A1 A2 A3 Ai i+1 i+1 5/19/2023 21 WinterCamp 2023 進(jìn)一步分析 ?這樣的詢問會不會問到底也沒法插入 i+1？ ?不會！因為 i+1有邊到 Ai。 1 5/19/2023 16 WinterCamp 2023 小結(jié) ?應(yīng)用這類二分枚舉的 最優(yōu)性問題 近來很是熱門（如 NOI2023樹的劃分），而且這類試題很容易誘導(dǎo)選手 直接 采用 動態(tài)規(guī)劃 或是 貪心算法，而走入死胡同。 5/19/2023 10 WinterCamp 2023 初步分析 ?由于 N很大，猜想可以通過貪心方法解決。 如果 ip，我們將范圍確定為 S中比 x小的元素，求該范圍內(nèi)第 i個
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1