K极值问题

2016-03-07  本文已影响0人  FTVBeginning

给定一个长度为N(0<n<=10000)的序列,保证每一个序列中的数字a[i]是小于maxlongint的非负整数 ,编程要求求出整个序列中第k大的数字减去第k小的数字的值m,并判断m是否为质数。(0<k<=n)
输入格式:第一行为2个数n,k(含义如上题)第二行为n个数,表示这个序列
输出格式:如果m为质数则第一行为'YES'(没有引号)第二行为这个数m否则 第一行为'NO'第二行为这个数m

include <iostream>

define MAXN 10000

using namespace std;
int main()
{
int i,n,k,a[MAXN] = {0}
int is_prime(int);
void sort(int ans[], int);
cin >> n >> k;
for(i=0; i<n; i++)
{
cin >> a[i];
}
sort(a,n);
if(is_prime (a[k-1]-a[n-k]))cout << "YES\n" << a[k-1]-a[n-k]<<endl;
else cout << "NO\n" << a[k-1]-a[n-k] << endl;
return 0;
}

int is_prime (int figure)
{
int i;
if(figure<2) return 0;
if(figure==2) return 1;
for(i=3;i<figure;i++)
{
if(figure % i== 0)return 0;
}
return 1;
}

void sort(int ans[], int length)
{
void swap(int *a, int *b);
int t,r;
for(t=0; t < length; t++)
{
r=1;
while(t-r >=0 && ans[t-r] < ans[t]
{
swap(&ans[t], &ans[t-r[);
t -= r;
}
}
}

void swap(int *a, int *b)
{
int t;
t = *a; *a = *b; *b = t;
}

上一篇下一篇

猜你喜欢

热点阅读