#9905: 不排序的解法


silithus (希利蘇斯)

學校 : 澳門培道中學
編號 : 33314
來源 : [60.246.116.246]
最後登入時間 :
2023-09-19 17:00:10
d153. 六、智力测验 -- NOI冬令营 | From: [60.246.134.23] | 發表日期 : 2015-06-11 21:42

TLE估計是因為用了低效的排序方法,對於沒有集成sort函數的語言(如PASCAL)又不想自己寫排序的話,可以用不排序的方法,效率比排序法更高:

#include <stdio.h>

int main(void)

{

int T,N,i,n,mid,sum;

int cnt[101];

scanf("%d", &T);

while( T-- ) {

for(i=0; i<=100; i++) cnt[i] = 0;

scanf("%d", &N);

for(i=0; i<N; i++) {

scanf("%d", &n);

cnt[n]++;

}

mid = N/2 + N%2;

for(n=sum=0; n<=100; n++) {

sum += cnt[n];

if( sum >= mid ) break;

}

 

printf("%d\n", n);

}

 

return 0;

}

 

 
ZeroJudge Forum