我又來了, 這表示有結果了 這題其實是ACM UVa的題目, 不用會員即可觀看的網址如下： http://zerojudge.tw/ShowProblem?problemid=d194 不論題目的描述, 就是求位置連續但數值相異的最長序列 如果以上一篇文提到的演算法在 Zero Judge 是可以 AC 的, 因為測資不到100萬個 但在 ACM UVa 那裡就行不通了,而且限定的秒數比一般3.000秒還短的是2.000秒 所以怎麼傳怎麼TLE 先把演算法化為程式, 跑一次的程式碼如下： ================================================== scanf("%d", &snowflakes[0]); for(i = 0, j = 1, max = 0; j < n; ++j) { scanf("%d", &snowflakes[j]); for(x = j - 1; x >= i; --x) { if(snowflakes[j] == snowflakes[x]) { if(max < j - i) { max = j - i; } i = x + 1; break; } } } if(max < j - i) { max = j - i; } printf("%d\n", max); ============================================== i 表示左指標, j 表示右指標 內for迴圈就是循序查找的過程 最差的情況(全部相異) 1 + 2 + 3 + 4 + ... + n 次 = (n * (n + 1)) / 2 大概是O(n^2)的等級 而我說過如果用 C++ 的 STL 的 map 會有比較快的解答 演算法其實是一樣的, 程式碼如下：(snowflake 在此是 map<int, int> ) ====================================================== max = left = 0; snowflakes.clear(); for (i = 1; i <= n; ++i) { scanf ("%d", &flake); if(left < snowflakes[flake]) { left = snowflakes[flake]; } snowflakes[flake] = i; if(max < i - left) { max = i - left; } } printf("%d\n", max); ====================================================== C++ 的寫法其速度大概是 C (上面那個程式) 的1/6倍 - 196ms 對 1.2s 而今天聽從網友的建議, 我去找了 C 的 Hash Table 的程式碼 經過修改後竟也過了, 其速度提升到 C++ 的1.5倍 - 276ms 可惜我改的這個程式是有版權的, 為表尊重不好公開, 但我提供網址如下： Google 搜尋 "c hash table" http://www.cl.cam.ac.uk/~cwc22/hashtable/ 這個網站主人實作了 C 的 hash table 程式 我的作法是將 標頭檔 和 .c檔 全部加在一起, 並修改 search 的函式 search 函式在找到相同的 key 值會以新的 data 值替代舊的 所以傳入一個指標去存舊的 data 值, 才能實行 left 和 舊data值 比對的 if 敘述 另外要自行找 hash function Google 搜尋 "hash function integer" http://www.concentric.net/~Ttwang/tech/inthash.htm 我用的是 Robert Jenkins' 32 bit integer hash function 這個 附帶一提的是, 網站主人所寫的 destroy hash table 程式似乎有問題 上傳都是 runtime error, 最後我索性用註解槓掉, 不 free 記憶體的結果才過的 不過這樣不太好, 但至少運算過程其答案是對的 最後感謝大家提供的寶貴意見, 忙了一天總算有點收穫 接下來是好好研究這些程式的寫法 Bleed -- World of bleed1979 http://bleed1979.myweb.hinet.net/ --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.168.133.60