跳至正文

TYVJ 第二题 第K极值

  • OI路程
  思路很简单, 将数据进行一次排序, 取第t个和倒数第t个, 然后倒数第t个减去第t个, 再判断差是否为素数..
  听前辈们说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;
}

发表评论

您的电子邮箱地址不会被公开。