淺談二分策略的應用-在線瀏覽
2025-02-24 12:56本頁面
【正文】 顯式 有序序列 隱含的退化了的 有序序列 5/19/2023 9 WinterCamp 2023 例二： BTP職業(yè)網(wǎng)球賽 ? [問題描述 ] N（ N≤65536） — 有 N頭奶牛（ N是 2P）參加網(wǎng)球淘汰賽。 K （ 1≤K≤N1） — 比賽既要講求實力，又要考慮到運氣。如果兩頭奶牛的排名相差大于給定整數(shù) K，則排名靠前的奶?？偸勤A排名靠后的奶牛；否則，雙方都有可能獲勝。并要求你列舉出一個可能的比賽安排使該奶牛獲勝。 K+1?1 K+2?2 … … 2K?K 3K+1?2K+1 … … … … 5/19/2023 11 WinterCamp 2023 初步分析 ?但我們很容易找到反例，例如： N=8, K=2 ?但最優(yōu)解為 6。 ?證明： ? 情況一： Y被 Z≠X擊敗 Z?? … Y ?? … X ?? Z? … ?? … ?? … ?? Y X X X YYYX5/19/2023 13 WinterCamp 2023 性質(zhì)：隱含的有序性 ? 如果 排名為 X的選手最終獲勝，那么 排名在 X前 的選手 Y也可以獲勝。 ?知道了 X，能否很快構造出對戰(zhàn)方式？ ?可以證明這樣貪心是正確的。 例如 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 小結 ?算法的根本 —— 在一個 隱含的退化了的 有序序列中進行二 分查找 0 0 0 0 0 0 0 0 1 1 1 1 1 1 XAns X≥Ans ?我們所尋找的 —— 兩種值的 分界點 。 ?所以，今后
教學課件相關推薦
鄂ICP備17016276號-1