Re: [問題] Uva 10020

看板C_and_CPP (C/C++)作者tropical72 (藍影)時間15年前 (2011/01/27 05:34)推噓4(4推 0噓 5→)

留言9則, 3人參與討論串1/2 (看更多)

: 大意：給一個 range[0, M]，有 n(n < 100001) 個 segment[L, R]，問最少用幾 : 個 segment 可以 cover 這個 range，如果沒有辦法 ouput 0，如果可以 : output segment 個數和所用的 segment(sorted L) 我先說您的程式碼我覺得奇怪的地方 1. scanf("%s%s", s1, s2); sscanf(s1, "%lf", &a); sscanf(s2, "%lf", &b); 為什麼不直接用 while(scanf("%lf%lf",&a,&b)==2) ? 2. 我不知道這題是不是有必要處理浮點數,不過也才 1E5, int 還存得下, 測資也沒出現過浮點數,如果可以只處理整數的話就用整數

推

Yshuan

01/26 23:31,

01/26 23:31

→

Yshuan

01/26 23:38,

01/26 23:38

→

tom1990

01/27 00:24,

01/27 00:24

→

tom1990

01/27 00:24,

01/27 00:24

這裡統整一下，這問題似乎是最小含蓋的基礎題，解法大致上樓上都點出來了，點進去看後發現測資還蠻特別的，再提幾個細節部份 1. 題目一開始就會給你 M 值，要包的範圍是 [0,M]，測資是給 [Li,Ri] 測資應有三種可以直接跳過不用讀進去 (a) Li == Ri --> 沒有貢獻度 (b) Ri <=0 --> 沒有貢獻度 (c) Li >= M --> 沒有貢獻度另外在掃的時候可以順便判斷下面這個 (a) 你掃過的資料沒有一個數字 >= M，這一定是無解。 2. 再來是 t 大說的，對 Li 做升冪排序, 至於 Ri 要不要排, 我是覺得可以不用排不知其他版友怎麼看 (排序速度可能是關鍵,因測資到10萬筆) 3. 假設挑出來測資排序後出來如下 [0,1] [0,3] [0,5] [0,10] [1,5] [1,6] [1,7] [1,10] [2,10] 首先先確認一件事，排下來的結果如果 "第一個區間" 的 Li > 0 那就直接跳出來，無解了。接著的確是 Y 大說的貪婪法, 同一個 Li 直接挑最後一筆出來即可, 但這裡必須再考慮 L1!=L2, R1=R2 的情況,以上面的情形,是只要挑 [0,10] 即可就完全不用再考慮 [1,10] [2,10] 問題, 我的想法是把 [0,10] 挑出來後,可以去找 Ri=10 的部份,那筆資料可以直接砍掉 ( 您的方法似乎就是這部份會出問題 ) 一個技巧是,多設一個變數 CurrentR, 紀錄目前最右邊是記到哪裡， if (Ri <= CurrentR) , 可以跳過不用理它了。 -------------------- 這題大概就這樣, 有高手想補充的話非常樂意, 此外還有其它的進階題 http://ds.fzu.edu.cn/fine/resources/download/bicov.pdf 有興趣的話再解解看最後的PS: 小聲的說,這個我覺得到 Prob_Solve 問比較適合 -- YouLoveMe() ? LetItBe() : LetMeFree(); -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 180.177.76.142 ※ 編輯: tropical72 來自: 180.177.76.142 (01/27 05:57)