淺談二分策略的應(yīng)用-文庫吧在線文庫
【正文】 行性問題 。 ?由此，我們得到了一種詢問方法，但最壞情況下總的詢問次數(shù)可能是 O(N2)的。我們不能讓二分思想僅僅停留在一般有序數(shù)組上的最基本的二分查找，而應(yīng)該擴展到更廣泛的應(yīng)用上。 ? 這樣，我們所需要的詢問次數(shù)僅為 O(nlogn)。 思考 . . . 5/19/2023 19 WinterCamp 2023 初步分析 ?為了避免詢問的盲目性，我們嘗試使用 增量法 逐步擴展序列。 ?知道了 X，能否很快構(gòu)造出對戰(zhàn)方式？ ?可以證明這樣貪心是正確的。如果兩頭奶牛的排名相差大于給定整數(shù) K，則排名靠前的奶牛總是贏排名靠后的奶牛；否則，雙方都有可能獲勝。二分策略 在信息學(xué)競賽中的 應(yīng)用 華東師大二附中 楊俊 5/19/2023 1 WinterCamp 2023 二分策略 ?來源 一個很簡單的想法 —— 在 最壞情況下 排除 盡可能多 的干擾，以盡可能快地求得目標(biāo) ?效率 高！對信息的充分利用，盡可能去除冗余 ，減少了不必要計算 ?應(yīng)用 廣！ 5/19/2023 2 WinterCamp 2023 三種應(yīng)用類型 ?類型一：二分查找 —— 應(yīng)用于一般有序序列 ?類型二：二分枚舉 —— 應(yīng)用于退化了的有序序列 ?類型三：二分搜索 —— 應(yīng)用于無序序列 5/19/2023 3 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?申明： “ 有序序列 ” ，僅包含兩層意思： ? 第一，它是一個 序列 ，一維的 ? 第二，該序列是 有序 的，即序列中的任意兩個元 素都是可以比較的，也就是擁有我們平時 所說的 全序關(guān)系 5/19/2023 4 WinterCamp 2023 類型一：二分查找 —— 應(yīng)用于一般有序序列 ?二分查找的一般實現(xiàn)過程： （ 1）確定查找范圍 （ 2）選擇基準(zhǔn)元素 （
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1