Tyvj_P1001 第K極值

P1001 第K極值 時間: 1000ms / 空間: 131072KiB / Java類名: Main

背景

成成第一次模拟賽 第一道

描述

給定一個長度為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

#include<stdio.h>
#include<math.h>
void merge_sort(__int64 *,int ,int ,__int64 *);
bool judge(__int64 );
int main()
{
	int n,k;
	__int64 a[10000],t[10000];
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++)
		scanf("%I64d",&a[i]);
	merge_sort(a,0,n,t);
	__int64 m=a[n-k]-a[k-1];
	if(judge(m)) printf("YES\n");
	else printf("NO\n");
	printf("%I64d",m);
	return 0;
}
void merge_sort(__int64 *a,int x,int y,__int64 *t)
{
	if(y-x>1)
	{
		int m=x+(y-x)/2;
		merge_sort(a,x,m,t);
		merge_sort(a,m,y,t);
		int p=x,q=m,i=x;
		while(p<m||q<y)
		{
			if(q>=y||p<m&&a[p]<a[q]) t[i++]=a[p++];
			else t[i++]=a[q++];
		} 
		for(i=x;i<y;i++)
		a[i]=t[i];
	}
}
bool judge(__int64 m)  //素數判斷 
{
	if(m<2) return false;  //小心那些小于2的數 
	if(m==2) return true;
	if(m%2==0) return false;
	for(int i=3;i<=sqrt(m);i+=2)
	{
		if(m%i==0) return false;
	}
	return true;
}
//bool  類型 在C中是過不了編譯的   但是在C++中可以過的了編譯 、、
//C标準中沒有bool類型