算法合集之淺談信息學競賽中的區(qū)間問題(編輯修改稿)
2024-11-12 20:32 本頁面
【文章內容簡介】 nilL???1m a x? 算法： ? 按最終期限排序 ? 順序安排各區(qū)間 最終期限 di ? 有 n個區(qū)間，選擇盡量少的區(qū)間，使得這些區(qū)間完全覆蓋某線段 [s,t]。 ? 算法： ? 按左端點坐標排序 ? 每次選擇覆蓋點 s的區(qū)間中右端點坐標最大的一個，并更新 s ? 直到所選區(qū)間已包含 t 、覆蓋問題 例題： USACO 2021 dec silver ? 倉庫從第 M秒到第 E秒的任意時刻都需要有人打掃。有 N個工人，每人給出自己的工作時間段：從第 T1秒到第 T2秒，需要支付工資 S元。 ? 錄用一部分人，要保證從 M秒到第 E秒的任意時刻都得有人打掃，問最少要付多少工資。 轉化 ? 問題轉化為：在一些帶權區(qū)間中，
教學課件相關推薦
鄂ICP備17016276號-1