作者tw00088437 (喵貓 loves fish)
看板C_and_CPP
標題[問題] 找兩個已排序陣列共同的數
時間Fri Dec 11 00:37:05 2009
( *[1m *[m 為色碼，可以按 Ctrl+V 預覽會顯示的顏色 )
( 未必需要依照此格式，文章條理清楚即可 )
遇到的問題： (題意請描述清楚)
TLE
http://zerojudge.tw/ShowProblem?problemid=d136
寫的改進版本第一個測資變快了 但是第二個測資還是TLE(1s)
希望得到的正確結果：
要如何加速？
我本身是從兩個陣列的第一個元素開始 如果比較小的那邊就作
binary search找到大於等於另外一個陣列的那個元素 直到底
程式跑出來的錯誤結果：
開發平台： (例: VC++ or gcc/g++ or Dev-C++, Windows or Linux)
有問題的code： (請善用置底文標色功能)
http://nopaste.csie.org/2771e
補充說明：
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.104.249
1F：推 ledia:1. 不要用 scanf, 用 getchar 來處理 input 12/11 00:45
2F：→ ledia:2. binary search 不見得比較快 12/11 00:46
3F：→ ledia:比如說一邊是 1 3 5 7 9, 一邊是 2 4 6 8 10 12/11 00:47
4F：→ ledia:binary search 沒辦法幫他跳很遠, 反而 overhead 變高了 12/11 00:47
5F：→ tw00088437:我擺過一些情形 好像比較稀疏的時候bs才比較快 12/11 00:55
6F：→ tw00088437:可是我也想不太到別的方法~"~ 12/11 00:55
7F：→ tw00088437:一個一個往上找和bs以外的@@? 12/11 00:55
8F：推 ledia:真的要 bs 的話, 請用 stack 版本, function call overhead 12/11 00:57
9F：→ ledia:在呼叫多次時也是很可觀的 12/11 00:57
10F：→ ledia:stack -> loop ...... 我在講什麼呀我 該睡了 XD 12/11 00:58
11F：→ bleed1979:擺2個哨兵跑一個迴圈 12/11 02:08
12F：推 bigpigbigpig:這一題問的其實就是 STL 中 set_intersection 的實作 12/11 21:32
13F：→ tw00088437:抱歉我嫩嫩的 聽不太懂呢 = =" 12/11 23:09