题目描述 Description
给定一个长度为N(0<n<=10000)的序列，保证每一个序列中的数字a[i]是小于maxlongint的非负整数 ，编程要求求出整个序列中第k大的数字减去第k小的数字的值m，并判断m是否为质数。(0<k<=n)
输入描述 Input Description
第一行为2个数n，k（含义如上题）
第二行为n个数，表示这个序列
输出描述 Output Description
如果m为质数则
第一行为'YES'(没有引号）
第二行为这个数m
否则
第一行为'NO'
第二行为这个数m
样例输入 Sample Input
5 2 1 2 3 4 5
样例输出 Sample Output
YES 2
数据范围及提示 Data Size & Hint
20%数据满足0<n<=10
50%数据满足0<n<=5000
100%数据满足0<n<=10000
分类标签 Tags 点此展开
题解：
nth_element开外挂了
使用方法：nth_element(start, start+n, end)
使第n大元素处于第n位置（从0开始,其位置是下标为n的元素），并且比这个元素小的元素都排在这个元素之前，比这个元素大的元素都排在这个元素之后，但不能保证他们是有序的。
AC代码：
#include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define N 10010 int n,k,a[N]; bool judge(int x){ if(x<2) return 0; for(int i=2;i<=sqrt(x);i++) if(x%i==0) return 0; return 1; } int main(){ scanf("%d%d",&n,&k); int t=n-k+1; for(int i=1;i<=n;i++) scanf("%d",&a[i]); nth_element(a+1,a+k,a+n+1); int kx=a[k]; nth_element(a+1,a+t,a+n+1); int kd=a[t]; int ans=kd-kx; puts(judge(ans)?"YES":"NO"); printf("%d ",ans); return 0; }