淺談二分策略的應(yīng)用(參考版)
2025-01-25 12:56本頁(yè)面
【正文】 5/19/2023 26 WinterCamp 2023 總結(jié) ?二分策略常與其它一些算法相結(jié)合，并借以隱蔽自己，逃離我們的視線。 ?這里我想指出的是：二分思想雖然簡(jiǎn)單，但是它的內(nèi)容還是非常豐富的。 i+1 i+1 A1 A[i/2] Ai i+1 5/19/2023 23 WinterCamp 2023 小結(jié) ?算法的根本 —— 在一個(gè)無(wú)序的 01序列中進(jìn)行二分查找 0 0 1 0 1 1 1 0 0 1 1 1 ?我們所尋找的 —— 一個(gè)特殊的子串‘ 01’ 0 1 5/19/2023 24 WinterCamp 2023 小結(jié) ?由此可見，這樣的二分搜索方法往往應(yīng)用于那些 可行解較多 ，但需要高效地 構(gòu)造一組可行解 的問(wèn)題。因此，我們可以用 二分搜索 來(lái)尋找 Ak，使 i+1可以插入 Ak與 Ak+1之間。 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。 A1 A2 A3 Ai i+1 i+1 5/19/2023 21 WinterCamp 2023 進(jìn)一步分析 ?這樣的詢問(wèn)會(huì)不會(huì)問(wèn)到底也沒法插入 i+1？ ?不會(huì)！因?yàn)?i+1有邊到 Ai。 ?我們先任意詢問(wèn)兩個(gè)點(diǎn) ?不妨設(shè)詢問(wèn)結(jié)果是 1到 2有邊，于是，我們就得到一條長(zhǎng)度為 1的線路。目標(biāo)是 詢問(wèn)次數(shù) 盡可能少。切記！? 退一步海闊天空 ?。 1 5/19/2023 16 WinterCamp 2023 小結(jié) ?應(yīng)用這類二分枚舉的 最優(yōu)性問(wèn)題 近來(lái)很是熱門（如 NOI2023樹的劃分），而且這類試題很容易誘導(dǎo)選手 直接 采用 動(dòng)態(tài)規(guī)劃 或是 貪心算法，而走入死胡同。 ?如果利用靜態(tài)排序二叉樹，整個(gè)問(wèn)題可以在O(Nlog2N)時(shí)間完成。 ?證明： ? 情況二： Y被 X擊敗 Y??
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1