淺談二分策略的應(yīng)用(編輯修改稿)
2025-02-10 12:56 本頁面
【文章內(nèi)容簡介】 erCamp 2023 初步分析 ?但我們很容易找到反例，例如： N=8, K=2 ?但最優(yōu)解為 6。 ?解決方法： 枚舉！ 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也可以獲勝。 ?證明： ? 情況一： Y被 Z≠X擊敗 Z?? … Y ?? … X ?? Z? … ?? … ?? … ?? Y X X X YYYX5/19/2023 13 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 ?證明： ? 情況二： Y被 X擊敗 Y?? … X ?? … ? … … ?? … ?? X X Y X YYY X5/19/2023 14 WinterCamp 2023 問題的解決 ?于是，我們可以 二分枚舉 獲勝的 X。 ?知道了 X，能否很快構(gòu)造出對戰(zhàn)方式？ ?可以證明這樣貪心是正確的。 ?如果利用靜態(tài)排序二叉樹，整個問題可以在O(Nlog2N)時間完成。 例如 N=8， K=2， X=6 6?7 5?3 4?8 2?1 6?5 4?2 6?4 可以！ 5/19/2023 15 WinterCamp 2023 小結(jié) ?算法的根本 —— 在一個 隱含的退化了的 有序序列中進(jìn)行二 分查找 0 0 0 0 0 0 0 0 1 1 1 1 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1