1 /*========================================== 2 P1001 第K极值 3 内存限制 128MB 代码限制 64KB 4 描述 Description 5 给定一个长度为N(0<n<=10000)的序列，保证每一个序列中的数字a[i]是 6 小于maxlongint的非负整数 ，编程要求求出整个序列中第k大的数字减去 7 第k小的数字的值m，并判断m是否为质数。(0<k<=n) 8 输入格式 InputFormat 9 输入格式： 10 第一行为2个数n，k（含义如上题） 11 第二行为n个数，表示这个序列 12 输出格式 OutputFormat 13 输出格式： 14 如果m为质数则 15 第一行为'YES'(没有引号） 16 第二行为这个数m 17 否则 18 第一行为'NO' 19 第二行为这个数m 20 样例输入 SampleInput 21 5 2 22 1 2 3 4 5 23 样例输出 SampleOutput 24 YES 25 2 26 27 数据范围和注释 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 最小的质数是2,如果小于2的话,请直接输出NO 39 ============================================*/ 40 #include<stdio.h> 41 #include<stdlib.h> 42 #include<math.h> 43 int fun(long n);//判断n是否质数，是则返回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 %ld ",m); 56 else printf("NO %ld ",m); 57 return 0; 58 } 59 int fun(long n)//判断n是否质数，是则返回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类型数据。要注意第k大数减去第k小数有可能是负数。质数检测也要注意写正确。可以使用快排的就用快排。
好久没写OJ的题目了，再过来看看写写倍觉亲切啊