2012年5月26日 星期六

tioj 1208 第K大連續和

二分搜答案 -> MergeSort求有多少個大於此答案

Merge Sort 那邊不太難,自己想(用雙指標,跟普通的Merge Sort差不多)

重點是二分搜答案的部份!!很容易沒想清楚TLE!!

這裡要來好好分析一下二分搜,不要再亂用猜的方式去寫答案

1. 最基本的:

while( lb < rb ){
        int mid = ( lb + rb ) / 2;
        if( ... ) lb = mid+1;
        else rb = mid;
}

想法:每次都減少範圍,直到 lb == rb。(... 為答案不可能是 mid 的情況)

證明:

當 rb - lb > 1時,rb >= lb+2,故mid >= lb+1(且mid < rb)

若情況為if,則範圍變小。若情況為else,則範圍亦變小。

當 rb - lb == 1 時,若 0 <= lb,則mid = lb,不管如何範圍都變小。

但若 lb < 0,則mid = rb,有可能範圍是不會變小的。(也就會引到TLE)


2. 較複雜的:

while( lb < rb-1 ){
       int mid = ( lb + rb ) / 2;
       if( ... ) lb = mid;
       else rb = mid;
}

 想法:rb 是指向最上界 + 1(... 為答案不可能是 mid 的情況)

證明:

當 rb - lb > 1時,一切都跟最基本的證明相同,無論如何範圍都會變小。

但是 rb 不會等於 lb+1,所以下面會引到TLE的點不存在,故不會引到TLE。


我的code:http://codepad.org/Gxh07Lzj

2 則留言: