【問題】請教兩題~

[嚴重過敏 10]

tioj 的1167題..

http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1167

和1287題

http://tioj.redirectme.net:8080/JudgeOnline/showproblem?problem_id=1287

兩題我都是同樣的問題~Time Limit Exceed

我都是用快速排序去找的~怎會超出時間呢?難道有更快的方法?還是我快速排序有寫錯?

以後是我寫的快速排序的程式碼

void sort(int x[],int left,int right)

{

int i,j,temp,k;

if(left<right)

{

i=left+1;

j=right;

k=x

;

do

{

while(x<k)

i++;

while(x[j]>k)

j--;

if(i<j)

{

temp=x; x=x[j]; x[j]=temp;

}

} while(i<j);

temp=x

; x

=x[j]; x[j]=temp;

sort(x,left,j-1);

sort(x,j+1,right);

}

}

感謝~xd

[arthurduh1 10]

好久沒上TIOJ了......

沒想到帳號密碼還記得起來XD

quicksort沒錯啊！

也許你該把完整程式碼po上來，

有可能在使用函數時弄錯了也說不定......

[arthurduh1 10]

哈，

我找到了！

要這樣才對唷！

void sort(int x[],int left,int right)

{

int i,j,temp,k;

if(left<right)

{

i=left+1;

j=right;

k=x

;

do

{

while(x<=k)

i++;

while(x[j]>k)

j--;

if(i<j)

{

temp=x; x=x[j]; x[j]=temp;

}

} while(i<j);

temp=x

; x

=x[j]; x[j]=temp;

sort(x,left,j-1);

sort(x,j+1,right);

}

}

錯的地方已經用紅色標起來！

如果沒等號的話，

有時候會導致無窮迴圈！！！

當然就TLE啦！

其實我跟quicksort不熟，

如果有高手發現還有錯，或有更好寫法歡迎指教。

SORRY，問題真的是出在quicksort上！

不過下次還是全部Po上來比較保險。

[嚴重過敏 10]

oh~我改了之後的確就AC. ==

這題我吃了5個TLE耶,.= =

:P

[嚴重過敏 10]

..不過腳踏車的還是沒過呢~= =

#include <stdio.h>

#include <stdlib.h>

void sort(int x[],int left,int right)

{

int i,j,temp,k;

if(left<right)

{

i=left+1;

j=right;

k=x

;

do

{

while(x<=k)

i++;

while(x[j]>k)

j--;

if(i<j)

{

temp=x; x=x[j]; x[j]=temp;

}

} while(i<j);

temp=x

; x

=x[j]; x[j]=temp;

sort(x,left,j-1);

sort(x,j+1,right);

}

}

int x[1000000];

int main(void)

{

int n,i,j,k;

while(scanf("%d%d",&n,&k)!=EOF)

{

if(n==0||k==0)

break;

for(i=0;i<n;i++)

scanf("%d",&x);

sort(x,0,n-1);

printf("%d\n",x[n-k]);

}

return 0;

}

以上為程式碼~感恩xd

[arthurduh1 10]

我懷疑quicksort還是有錯

而且我用C++內建函式庫的qsort就AC了= =

有沒有高手可以講解一下，

我怕我會說錯......

對了，

你叫ignored對不對？

內建函式庫寫法：

#include <stdio.h>

#include <cstdlib> //qsort所在函式庫(記得改！！！)

int compare_ints( const void* a, const void* b ) {

int* arg1 = (int*) a;

int* arg2 = (int*) b;

if( *arg1 < *arg2 ) return -1;

else if( *arg1 == *arg2 ) return 0;

else return 1;

}

int x[1000000];

int main(void)

{

int n,i,j,k;

while(scanf("%d%d",&n,&k))

{

if(n==0||k==0)

break;

for(i=0;i<n;i++)

scanf("%d",&x);

for(i=1;i<n;i++)if(x[i-1]>x)break;

if(i!=n)qsort( x, n, sizeof(int),compare_ints);

printf("%d\n",x[n-k]);

}

return 0;

}

其中紅字部分我有改過，

因為我本來想說會不會是有些測資是已經排序好的Sample，

用quicksort會特別慢。

後來我有把紅字改回來再試一次，

發現多了156ms

果然有差......

[嚴重過敏 10]

恩..原來還有內建的阿..

解了30幾題就遇到很大瓶頸~ˊˋ

很多座標的問題我都很不會處理說~ˊˋ

[嚴重過敏 10]

恩..我記得快速排序法除了找第一個當鍵值外

找中間數為鍵值時效率似乎較好??

可以請問怎麼寫嗎?@@

[嚴重過敏 10]

我去查了一下中間鍵值的方法..

結果就AC了~xd

修改後的程式碼如下

#include <stdio.h>

#include <stdlib.h>

void sort(int x[],int left,int right)

{

int i,j,temp,k;

if(left<right)

{

i=left-1;

j=right+1;

k=x[(left+right)/2];

while(1)

{

while(x[++i]<k);

while(x[--j]>k);

if(i >= j)

break;

temp=x; x=x[j]; x[j]=temp;

}

sort(x,left,i-1);

sort(x,j+1,right);

}

}

int x[1000000];

int main(void)

{

int n,i,j,k;

while(scanf("%d%d",&n,&k)!=EOF)

{

if(n==0||k==0)

break;

for(i=0;i<n;i++)

scanf("%d",&x);

sort(x,0,n-1);

printf("%d\n",x[n-k]);

}

return 0;

}

速度是1484MS

的確快了很多喔

[arthurduh1 10]

其實如果真的是隨機的資料，

不管用哪裡當鍵值平均速度都是一樣的！！！

而且用了「除以」這項(奢侈的)運算其實會更花時間。

那你知道為什麼以第一個當鍵值會特別慢嗎？

因為設計測資的人知道，

大部分的人都會用第一個當鍵值，

所以就會故意放幾個(或很多個)幾近排序完成的測資，

這對以第一個當鍵值的quicksort是很傷的，

會造成n^2級的運算時間= =

其實不管用哪裡當鍵值，

都會有特別慢的情況出現，

只是用中間當鍵值會是比較保險的作法！！！

(不知道No1的265MS是怎麼做出來的= =

好可怕......)

[su_horng 10]

建議在索尼小站或直接在TIOJ的Web Board問

這裡還挺冷清的

索尼小站telnet://sony.twbbs.org譬如說sa072686版或SKYLY版或shik版XD

順帶一提

找第k大的數有O(n)作法

[文旋 10]

建議在索尼小站或直接在TIOJ的Web Board問

這裡還挺冷清的

索尼小站telnet://sony.twbbs.org譬如說sa072686版或SKYLY版或shik版XD

順帶一提

找第k大的數有O(n)作法

可以教一下找第k大的O(n)做法是如何嗎?

[jeremy89183 10]

腳踏車那題真的不知道25X怎麼跑的= ="

輸入優化+中間鍵值還是有328...

[jeremy89183 10]

可以教一下找第k大的O(n)做法是如何嗎?

TIOJ上的"蛋糕內的信物"我們校內講議是說要O(n)...

但我用qsort再搜也過了@@

不然用內建函式nth_element也可以(小聲..