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