算法合集之淺談信息學競賽中的區(qū)間問題-資料下載頁
2024-10-16 20:32本頁面
【正文】 按左端點坐標排序 ? 維護一個二叉堆，以 f值為關鍵字 ? 狀態(tài)轉移 （刪除右端點坐標太小的區(qū)間） ? 有 n個區(qū)間， m個點。若某區(qū)間包含了某點，則構成一對匹配關系。選出最多的區(qū)間和相同數(shù)量的點，使對應的區(qū)間和點構成匹配關系。 算法： ? 所有點按坐標排序 ? 選取包含該點且右端點坐標最小的區(qū)間 優(yōu)化 ? 按區(qū)間左端點排序，得到有序表 ? 維護二叉堆，以區(qū)間右端點為關鍵字 ? 所有點按坐標從小到大依次處理 維護二叉堆： 插入左端點小于等于該點坐標的區(qū)間 刪除右端點小于該點坐標的區(qū)間 取出右端點坐標最小的與該點匹配并刪除 總結 ? 有序性 ? 算法的選擇 ? 優(yōu)化 —— 數(shù)據(jù)結構的選擇
教學課件相關推薦
鄂ICP備17016276號-1