1 /*========================================== 2 P1001 第K極值 3 內存限制 128MB 代碼限制 64KB 4 描述 Description 5 給定一個長度為N(0<n<=10000)的序列，保證每一個序列中的數(shù)字a[i]是 6 小于maxlongint的非負整數(shù) ，編程要求求出整個序列中第k大的數(shù)字減去 7 第k小的數(shù)字的值m，并判斷m是否為質數(shù)。(0<k<=n) 8 輸入格式 InputFormat 9 輸入格式： 10 第一行為2個數(shù)n，k（含義如上題） 11 第二行為n個數(shù)，表示這個序列 12 輸出格式 OutputFormat 13 輸出格式： 14 如果m為質數(shù)則 15 第一行為'YES'(沒有引號） 16 第二行為這個數(shù)m 17 否則 18 第一行為'NO' 19 第二行為這個數(shù)m 20 樣例輸入 SampleInput 21 5 2 22 1 2 3 4 5 23 樣例輸出 SampleOutput 24 YES 25 2 26 27 數(shù)據(jù)范圍和注釋 Hint 28 對于第K大的詳細解釋: 29 如果一個序列為1 2 2 2 2 3 30 第1大 為3 31 第2大 為2 32 第3大 為2 33 第4大 為2 34 第5大 為1 35 第K小與上例相反 36 37 另外需要注意的是 38 最小的質數(shù)是2,如果小于2的話,請直接輸出NO 39 ============================================*/ 40 #include<stdio.h> 41 #include<stdlib.h> 42 #include<math.h> 43 int fun(long n);//判斷n是否質數(shù)，是則返回1，否則返回0； 44 int cmp(const void *a,const void *b); 45 int main() 46 { 47 long n,k,*a,i,m; 48 scanf("%ld%ld",&n,&k); 49 a=(long *)malloc(n*sizeof(long)); 50 for(i=0;i<n;i++) 51 scanf("%ld",&a[i]); 52 qsort(a,n,sizeof(long),cmp); 53 m=a[n-k]-a[k-1]; 54 i=fun(m); 55 if(i==1) printf("YES\n%ld\n",m); 56 else printf("NO\n%ld\n",m); 57 return 0; 58 } 59 int fun(long n)//判斷n是否質數(shù)，是則返回1，否則返回0； 60 { 61 long i,t; 62 if(n<2) return 0; 63 t=sqrt(n); 64 for(i=2;i<=t;i++) 65 { 66 if(n%i==0) return 0; 67 } 68 return 1; 69 } 70 int cmp(const void *a,const void *b) 71 { 72 return *(long *)a-*(long *)b; 73 }

這個題呢要用long類型數(shù)據(jù)。要注意第k大數(shù)減去第k小數(shù)有可能是負數(shù)。質數(shù)檢測也要注意寫正確。可以使用快排的就用快排。

?

好久沒寫OJ的題目了，再過來看看寫寫倍覺親切啊

轉載于:https://www.cnblogs.com/huashanqingzhu/p/3831670.html

總結

以上是生活随笔為你收集整理的P1001 第K极值【tyvj】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。