#39: 懇求此題之解!!


YIEC2538 (unknown)

學校 : 不指定學校
編號 : 334
來源 : [123.194.188.121]
最後登入時間 :
2022-10-23 11:16:29
d061. Q-4-20. 監看華山練功場 -- AP325 | From: [162.158.119.197] | 發表日期 : 2020-12-06 17:00

小弟我寫了半天還是 Debug 不出來,或找到更好更有效率的思路,懇請大神幫忙 ~~

感謝!!

 
#40: Re:懇求此題之解!!


810848 (路過)

學校 : 一中
編號 : 96
來源 : [36.234.120.232]
最後登入時間 :
2024-01-27 14:43:50
d061. Q-4-20. 監看華山練功場 -- AP325 | From: [162.158.118.106] | 發表日期 : 2020-12-08 23:52

小弟我寫了半天還是 Debug 不出來,或找到更好更有效率的思路,懇請大神幫忙 ~~

感謝!!



先依左界排序,然後刪除不必要的地方([x,y]以外)

假設0~i-1已經選完了,設選出來的集合=S,此時有幾種狀況:

1. i的右邊在S最右邊的左邊,那i肯定不用選

2. i的左邊比S還右邊,那就無解,因為中間會有空隙

3. i不符合1跟2,那就選i,令S中第k右邊的線段=S(k),如果S(2)右邊 >= i左邊,那S(1)就沒用了,可以丟掉,然後以此類推...,可以看出這是stack的專長。

 
#41: Re:懇求此題之解!!


YIEC2538 (unknown)

學校 : 不指定學校
編號 : 334
來源 : [123.194.188.121]
最後登入時間 :
2022-10-23 11:16:29
d061. Q-4-20. 監看華山練功場 -- AP325 | From: [103.22.201.166] | 發表日期 : 2020-12-10 19:02

小弟我寫了半天還是 Debug 不出來,或找到更好更有效率的思路,懇請大神幫忙 ~~

感謝!!



先依左界排序,然後刪除不必要的地方([x,y]以外)

假設0~i-1已經選完了,設選出來的集合=S,此時有幾種狀況:

1. i的右邊在S最右邊的左邊,那i肯定不用選

2. i的左邊比S還右邊,那就無解,因為中間會有空隙

3. i不符合1跟2,那就選i,令S中第k右邊的線段=S(k),如果S(2)右邊 >= i左邊,那S(1)就沒用了,可以丟掉,然後以此類推...,可以看出這是stack的專長。

感謝你的救援!!  按照你的思路,簡單易懂,我終於 AC 那題了,好感動!


 

 
ZeroJudge Forum