[問題] Uva 10020

[tom1990 (湯姆祥)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 
GCC

額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 


問題(Question)：
Wrong answer

餵入的資料(Input)：
sample 和 forum 測資都正確

預期的正確結果(Expected Output)：


錯誤結果(Wrong Output)：


程式碼(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 是浮點數的問題。


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.167.137.126
推 Yshuan:我不太懂妳的演算法如何保證使用個數最小
→ Yshuan:我的話cmp會多個條件 if both head are equal, cmp tail
→ Yshuan:for(i=now=0;now<n(seg);) {
→ Yshuan:    while(seg[i].head<now)++i;
→ Yshuan:    choos seg[i] as a answer; now = seg[i].tail + 1;
→ Yshuan:    if( now > m) break; // find all answer
→ Yshuan:}  greedy的做法吧
→ tom1990:對應該也要比較 segment 長度，我是想在符合 left pointer
→ tom1990:裡面所有人去掃找出可以到最遠的 right pointer
→ tom1990:找到的答案應該是在 optimal solution 裡面且變成子問題
推 suhorng:做法看起來對
→ suhorng:可能是浮點數誤差,試試看純用int ...
→ suhorng:感覺你對這個做法的實做有點奇怪...