首页 > 代码库 > 1979 第K个数
1979 第K个数
1979 第K个数
时间限制: 1 s
空间限制: 1000 KB
题目等级 : 黄金 Gold
题目描述 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 21 2 3 4 5
样例输出 Sample Output
YES2
数据范围及提示 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 10010int 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\n",ans); return 0;}
1979 第K个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。