时间戳

首页 > 技术文章 > TYVJ P1001 第K极值 Label：水

TYVJ P1001 第K极值 Label：水

radiumlrb 2016-08-24 13:05 原文

背景

成成第一次模拟赛 第一道

描述

给定一个长度为N(0<n<=10000)的序列，保证每一个序列中的数字a[i]是小于maxlongint的非负整数 ，编程要求求出整个序列中第k大的数字减去第k小的数字的值m，并判断m是否为质数。(0<k<=n)

输入格式

输入格式：
第一行为2个数n，k（含义如上题）
第二行为n个数，表示这个序列

输出格式

输出格式：
如果m为质数则
第一行为'YES'(没有引号）
第二行为这个数m
否则 
第一行为'NO'
第二行为这个数m

测试样例1

输入

5 2 
1 2 3 4 5

输出

YES 
2

备注

对于第K大的详细解释:
如果一个序列为1 2 2 2 2 3
第1大 为3
第2大 为2
第3大 为2
第4大 为2
第5大 为1
第K小与上例相反

另外需要注意的是
最小的质数是2,如果小于2的话,请直接输出NO

代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int a[50005],m,N,K;
 8 int check(int x){
 9     if(x<=1) return 0;
10     for(int i=2;i<=sqrt(x);i++)//当x=2或3时，sqrt都为1
11         if(x%i==0) return 0;
12     return 1;
13 }
14 int main(){
15 //  freopen("01.txt","r",stdin);
16     scanf("%d%d",&N,&K);
17     for(int i=1;i<=N;i++)
18         scanf("%d",&a[i]);
19 
20     sort(a+1,a+N+1);
21     m=a[N-K+1]-a[K];
22     
23     if(check(2))
24         cout<<"YES"<<endl<<m<<endl;
25     else
26         cout<<"NO"<<endl<<m<<endl;
27     return 0;
28 }

 

推荐阅读