推 tom1990:謝謝你 AC了!!! 拿掉break多一個while條件判斷~ 01/27 12:53
→ tom1990:用int就可以... 01/27 13:06
→ suhorng:XD 01/27 13:06
附上我的實現... http://paste.plurk.com/show/359069/
※ 編輯: suhorng 來自: 61.217.31.101 (01/28 08:38)
※ 引述《tom1990 (湯姆祥)》之銘言：
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: http://paste.plurk.com/show/358421/
: 補充說明(Supplement)：
: 題目：http://acm.uva.es/problemset/v100/10020.html
: 大意： 給一個 range[0, M]，有 n(n < 100001) 個 segment[L, R]，問最少用幾
: 個 segment 可以 cover 這個 range，如果沒有辦法 ouput 0，如果可以
: output segment 個數和所用的 segment(sorted L)
: 解法： 先對 segment 的 L 排序，去除 segment 在 [0, M] 之外，記錄一個 left
: 表示目前的 range [left, M] 和一個 right 表示目前可以到的最右邊範圍
: ，掃一次 sorted array 如果 segment 符合 L <= left && R > left
: ，segment 的 R update right，再用 right update left並儲存所得
: segment，如果最後 left >= M 表示可以 cover。
: 中間有處理 segment 是浮點數的問題。
你的想法是對的,不過演算法實做錯了
另外 t 板友、Y 板友提出來的方法其實跟本串原PO差不多,
不過私心喜歡本串原PO的演算法XD 實做起來比較簡潔
依照你的演算法,以下這筆測資應該要跑出正確的答案:
1
7
0 4
1 6
2 4
3 7
0 0
可是你的程式卻輸出錯的答案...
這題可能有多組解,但既然題目沒有說也不之道有沒有special judge就忽略吧...
此外就是浮點數誤差,建議用int...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.217.31.101