POJ 2653 Pick-up sticks 題解
2021-03-29 22:29 作者:昵稱不能為空voidf | 我要投稿
題目大意:按時(shí)間順序往平面上扔線段,后來的會壓住先來的。問扔完后沒有被壓住的線段(頂層線段)有哪些。線段數(shù)量規(guī)模1e5,但保證答案不超過1e3。
思路:考慮每次新扔進(jìn)來的線段,它一定會成為當(dāng)前狀態(tài)的頂層線段,并且有可能壓住目前在頂層的一些線段。那么我們只需要維護(hù)一個(gè)當(dāng)前頂層的線段的集合,然后每次用新加入的一條線段去濾掉一些被壓住的即可。
這里選擇使用list處理,注意C++98的編譯器不支持嵌套模板兩個(gè)右尖括號的寫法,必須得空一格。
標(biāo)簽: