算法合集之一類算法復合的方法(已修改)
2024-10-28 20:29 本頁面
【正文】 一類算法復合的方法 江蘇省揚州中學 張煜承 問題描述 ?維護集合 S，初始時為空。有 N個操作需要依次處理 ?B X 在 S中插入一個整數(shù) X ?A Y 詢問 S中被 Y除余數(shù)最小的數(shù)，如果有多個則任取一個 ?1≤N≤40000， 1≤X,Y≤R=500000 ?允許離線算法 初步分析 ?算法 1：對詢問中每個不同的 Y， 維護它對應的詢問當前的答案 ?時間復雜度為 O(N2)，不能解決問題 ?但當詢問中出現(xiàn)的不同 Y的個數(shù)比較少時會很快，時間復雜度可以寫成 O(不同 Y的個數(shù) N) 進一步分析 ?當遇到一個詢問 A Y時，要在 S中尋找使得 x mod Y最小的數(shù) x ?把這里的 x寫成 kY+r，其中 0≤rY， k和 r是整數(shù) ?也就是說，
教學課件相關(guān)推薦
鄂ICP備17016276號-1