Re: [問題] Uva 10020

[tropical72 (藍影)]

: 大意：  給一個 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:我不太懂妳的演算法如何保證使用個數最小
→ Yshuan:}  greedy的做法吧
→ tom1990:對應該也要比較 segment 長度，我是想在符合 left pointer
→ tom1990:裡面所有人去掃找出可以到最遠的 right pointer
這裡統整一下，這問題似乎是 最小含蓋 的基礎題，
解法大致上樓上都點出來了，點進去看後發現測資還蠻特別的，
再提幾個細節部份

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)
推 suhorng:你連結的這題跟原PO的題目重點不同...
→ suhorng:而且連結中的應該是二分圖才對...?
→ suhorng:這兩個問題好像完全不一樣耶...
推 tom1990:謝謝你~ 我看forum上面測資有夾雜int和double所以想說用
→ tom1990:sscanf來解決
推 tom1990:測資只會有int...
→ tropical72:嗯,只是在我看來那連結也是最小含蓋問題 XD
推 suhorng:嗯@@ 我覺得二分圖最小點覆蓋 跟這題的線段覆蓋不同
→ suhorng:模型也無法轉過去的樣子