7.3 排序中的数学问题

“排序还可以帮助我们解决一些有趣的数学问题，”我说道，”比如判断质数，或者计算中位数。”

7.3.1 第K大与第K小数

题目描述： 给定一个长度为 N ( 0<n≤10000 )的序列，保证每一个序列中的数字 a[i] 是正整数且唯一 ，编程要求求出整个序列中第 k 大的数字减去第 k 小的数字的值 m ，并判断 m 是否为质数。

输入格式： 第一行为 2 个数 n，k（含义如上题）；第二行为 n 个数，表示这个序列。

输出格式： 如果 m 为质数,则第一行为YES,第二行为这个数 m; 否则 ，第一行为NO ，第二行为这个数 m。

样例输入：

5 2
1 2 3 4 5

样例输出：

YES
2

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, k;
    int a[10010];
    cin >> n >> k;
    
    for(int i = 1; i <= n; i++) 
        cin >> a[i];  // 输入序列
    
    // 冒泡排序，按降序排列
    for(int i = 1; i < n; i++){
        for(int j = 1; j <= n-i; j++){
            if(a[j] < a[j+1])
                swap(a[j], a[j+1]);
        }
    }
    
    int m = a[k] - a[n+1-k];  // 第k大减去第k小
    
    // 判断m是否为质数
    bool is_prime = true;
    if(m < 2) is_prime = false;  // 小于2的数不是质数
    
    for(int i = 2; i * i <= m; i++){  // 检查是否有因数
        if(m % i == 0){
            is_prime = false;
            break;
        }
    }
    
    if(is_prime) 
        cout << "YES" << endl;
    else 
        cout << "NO" << endl;
    cout << m << endl;
    return 0;
}

算法解析：

1. 对数组进行降序排序
2. 第k大的数是a[k]，第k小的数是a[n+1-k]
3. 计算差值m
4. 判断m是否为质数（检查2到√m范围内是否有因数）