算法合集之問題中的變與不變-閱讀頁
2024-10-31 20:36本頁面
【正文】 ? 另 Ci表示當前 Ai與它匹配的 Bj的距離。 找出 Ci中蘊含的不變？ 觀察 Ci ? 由于 Ai到 Bj有順時針，逆時針 2種走法。 ? 不妨把 Ci看成 Ai和 Bj的函數(shù)。 ? f(Ai)在枚舉和 A1匹配的點 Bk的過程中 只會發(fā)生 4次變化。 ? 當 A1匹配 Bk+1， 更新 f(Ai),g(Bi),sum。 ? [4]輸出 ?時間復雜度 ?O(排序 +事件總數(shù) )=O(nlgn) 小結 ? 將變化的 Ci轉化成 “ 不變 ” 的 f(Ai)和g(Bi) ? 減少了操作規(guī)模 ? 問題迎刃而解 總結 ? [例一 ]螞蟻 ? 以不變應萬變 ? [例二 ]circular way ? 將變量的操作規(guī)?？s小 仔細分析，大膽猜想 把握問題的本質 問題迎刃而解 變 不變 ? 參考文獻 : ? [1] 劉汝佳 ,黃亮 .算法藝術與信息學競賽 . 清華大學出版社 .2021 ? [2] zju online judge 2376 ants. ? [3] sgu online judge 313 circular railway.
教學課件相關推薦
鄂ICP備17016276號-1