如題，不知道出題者出這兩題有什麼差?

另外，題目當中"229!"是什麼意思?

那個.......這題測資待加強,沒錯,"加強"

另外229是 某三個英文字的大寫總合

其實可以只出第2題就好了

因為第2題要字串分析測資又比較強

看錯.....當我沒說......

 各位過快排這兩題都是直接調用c/c++函數的嗎? 

(抱頭~~~)嗄嗄嗄嗄嗄嗄嗄嗄

哈哈哈!

到最後變成只是開陣列大小的不同= = 

話說 ,三樓大大適用哪一個函式才這麼快阿?

我是用STL裡的sort()

另外，其實之前也有一題快排，一開始真的是自己打的

跟函式跑起來沒什麼差

 

其實可以只出第2題就好了

因為第2題要字串分析測資又比較強

快排(一)還是Uva的啊... 

看錯.....當我沒說......

 各位過快排這兩題都是直接調用c/c++函數的嗎? 

看程式碼長短就知道了XD....

(抱頭~~~)嗄嗄嗄嗄嗄嗄嗄嗄

哈哈哈!

到最後變成只是開陣列大小的不同= = 

 

話說 ,三樓大大適用哪一個函式才這麼快阿?

我是用STL裡的sort()

 

另外，其實之前也有一題快排，一開始真的是自己打的

跟函式跑起來沒什麼差

 

 

我也用std::sort() (攤手

std::sort()是非常優化過的排序算法

會判斷當下適合用哪種排序方式

例如當遞迴到n夠小時還會轉用O(n^2)的排序法

 

其實可以只出第2題就好了

因為第2題要字串分析測資又比較強

快排(一)還是Uva的啊... 

看錯.....當我沒說......

 各位過快排這兩題都是直接調用c/c++函數的嗎? 

看程式碼長短就知道了XD....

(抱頭~~~)嗄嗄嗄嗄嗄嗄嗄嗄

哈哈哈!

到最後變成只是開陣列大小的不同= = 

 

話說 ,三樓大大適用哪一個函式才這麼快阿?

我是用STL裡的sort()

 

另外，其實之前也有一題快排，一開始真的是自己打的

跟函式跑起來沒什麼差

 

 

我也用std::sort() (攤手

std::sort()是非常優化過的排序算法

會判斷當下適合用哪種排序方式

例如當遞迴到n夠小時還會轉用O(n^2)的排序法

如果可以的話,請各位AC的前輩們

對著排二寫個 正常遞迴qsort看看 (CRLS版)....

我的意思大概就傳達一半了 (當然也可以用在一,不過)

我想把快排砍掉啊, O(nlogn)
數字個數 500萬以上, 速度差 400 ms,
只怕出了變垃圾題,

1000萬個數字, 速度差 1500 ms 

 寫一個

qsrot(a,p,r);
if p<r then
   q<-parition(a,p,r);
   qsort(a,p,q-1);
   qsort(a,q+1,r);
end;

的版本看看..

我只是想說, O(nlogn) 不是最快的,
線性的演算法, 在 n 越大, 速度差距會拉開, 不過 ZJ 的測資檔不可能太大,
拉開一點, 也刷不掉那些用 nlogn 的使用者

亂數種子在 ZJ, 真是苦了我,

在之前的電腦 C/C++, rand()的範圍是在 0~32767,

上傳在 ZJ 的時候, 卻發現 ZJ 的系統, 回傳的範圍 0~2147483647

為了卡範圍, 我用 rand()*rand() 來補足 (32767*32767)

很帥氣地吃了一個 overflow, (2147483647*2147483647)

近似 O(N^2) 的 分堆插入法, 得 AC 了

總共分了 419,4304 堆

被隱蔽了w

可以說出題的原因了

出題原本的的希望是 c  qsort() 要TLE

沒錯,TLE :D (題目內所有的快速排序都是誘導要用quicksort的字眼......)

 

請別忘記qsort的最差情形是 O(n^2)

A Killer Adversary for Quicksort
http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

http://igoro.com/archive/quicksort-killer/

http://zeuxcg.org/2010/10/25/quicksort-killer-sequence/

不過我的測資太弱了......只對正常遞迴版本有影響 =_ = (20w 6xxs)

liou大一過就傻了XDDD  (是用randomize qsort)

真正的killer 是連randomize都可以作掉的   (有人可以生成測資嗎....)

感覺頗麻煩的= =

 grd加油...