思路很简单, 将数据进行一次排序, 取第t个和倒数第t个, 然后倒数第t个减去第t个, 再判断差是否为素数..
听前辈们说NOIp不能使用库函数qsort, 而我一老使用, 为了避免考试0分的情况, 这里就自己写了一个快排, 当快拍的元素少于15个时就使用插入排序进行排序.
代码如下:
听前辈们说NOIp不能使用库函数qsort, 而我一老使用, 为了避免考试0分的情况, 这里就自己写了一个快排, 当快拍的元素少于15个时就使用插入排序进行排序.
代码如下:
#include <stdio.h>
#include <math.h>
#define swap(a, b) do{\
if(!((a) ^ (b))){\
break;\
}\
(a) ^= (b);\
(b) ^= (a);\
(a) ^= (b);\
}while(0)
unsigned long map[10000];
int compare(int a, int b)
{
return a – b;
}
void insert_sort(unsigned long *a, int start, int end)
{
int i, j;
int key;
for(i = start + 1; i <= end; i++){
key = a[i];
for(j = i – 1; j >= 0 && compare(key, a[j]) < 0; j–){
a[j + 1] = a[j];
}
a[j + 1] = key;
}
}
int getmiddle(unsigned long a[], int s, int e)
{
int m;
m = (s + e) / 2;
if(compare(a[m], a[s]) < 0){
swap(a[m], a[s]);
}
if(compare(a[s], a[e]) > 0){
swap(a[s], a[e]);
}
if(compare(a[m], a[e]) > 0){
swap(a[m], a[e]);
}
return m;
}
void quick_sort(unsigned long *a, int start, int end)
{
int middle;
int len = end – start + 1;
int i, j;
unsigned key;
if(len <= 15){
insert_sort(a, start, end);
return;
}
middle = getmiddle(a, start, end);
key = a[middle];
swap(a[end – 1], a[middle]);
i = start; //除去三值的头
j = end – 1; //除去三值的尾
while(i < j){
while(compare(a[++i], key) < 0){
}
while(compare(a[–j], key) > 0){
}
if(i < j){
swap(a[i], a[j]);
}
}
swap(a[i], a[end – 1]);
quick_sort(a, start, i – 1);
quick_sort(a, i + 1, end);
}
int isprime(unsigned long n)
{
int limit = sqrt(n);
int i;
if(n == 1 || n == 0){
return 0;
}
for(i = 2; i <= limit; i++){
if(n % i == 0){
return 0;
}
}
return 1;
}
int main(void)
{
int n, t, i;
unsigned long ans;
scanf(“%d%d“, &n, &t);
for(i = 0; i < n; i++){
scanf(“%d“, &map[i]);
}
quick_sort(map, 0, n – 1);
ans = map[n – t] – map[t – 1];
if(isprime(ans)){
printf(“YES\n“);
}else{
printf(“NO\n“);
}
printf(“%d\n“, ans);
return 0;
}
#include <math.h>
#define swap(a, b) do{\
if(!((a) ^ (b))){\
break;\
}\
(a) ^= (b);\
(b) ^= (a);\
(a) ^= (b);\
}while(0)
unsigned long map[10000];
int compare(int a, int b)
{
return a – b;
}
void insert_sort(unsigned long *a, int start, int end)
{
int i, j;
int key;
for(i = start + 1; i <= end; i++){
key = a[i];
for(j = i – 1; j >= 0 && compare(key, a[j]) < 0; j–){
a[j + 1] = a[j];
}
a[j + 1] = key;
}
}
int getmiddle(unsigned long a[], int s, int e)
{
int m;
m = (s + e) / 2;
if(compare(a[m], a[s]) < 0){
swap(a[m], a[s]);
}
if(compare(a[s], a[e]) > 0){
swap(a[s], a[e]);
}
if(compare(a[m], a[e]) > 0){
swap(a[m], a[e]);
}
return m;
}
void quick_sort(unsigned long *a, int start, int end)
{
int middle;
int len = end – start + 1;
int i, j;
unsigned key;
if(len <= 15){
insert_sort(a, start, end);
return;
}
middle = getmiddle(a, start, end);
key = a[middle];
swap(a[end – 1], a[middle]);
i = start; //除去三值的头
j = end – 1; //除去三值的尾
while(i < j){
while(compare(a[++i], key) < 0){
}
while(compare(a[–j], key) > 0){
}
if(i < j){
swap(a[i], a[j]);
}
}
swap(a[i], a[end – 1]);
quick_sort(a, start, i – 1);
quick_sort(a, i + 1, end);
}
int isprime(unsigned long n)
{
int limit = sqrt(n);
int i;
if(n == 1 || n == 0){
return 0;
}
for(i = 2; i <= limit; i++){
if(n % i == 0){
return 0;
}
}
return 1;
}
int main(void)
{
int n, t, i;
unsigned long ans;
scanf(“%d%d“, &n, &t);
for(i = 0; i < n; i++){
scanf(“%d“, &map[i]);
}
quick_sort(map, 0, n – 1);
ans = map[n – t] – map[t – 1];
if(isprime(ans)){
printf(“YES\n“);
}else{
printf(“NO\n“);
}
printf(“%d\n“, ans);
return 0;
}