我又来了, 这表示有结果了 这题其实是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