完善程序（一）- 选择数对

题目描述

（选择数对） 有 n 个小朋友分别拿着一个数字，现在要求你将小朋友两两配对，要求每对小朋友手上的数字之差大于给定值 k。问最多可以从数组中选出多少对符合条件的小朋友。（每个小朋友最多只能和另外一个小朋友配对，不能脚踏两条船）

输入格式： 第一行给出 n, k 分别表示小朋友的个数，以及参数 k。接下来给出 n 个数字，表示每个小朋友手上的数字。

数据范围： 1 ≤ n, k ≤ 10⁵

提示： 二分最终的结果，对于二分的结果 mid，在 check 函数中 O(n) 判断能否选出 mid 对小朋友符合要求，最终保留二分的结果。

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn], n, k;
bool check(int mid) { // 要配对 mid 队
    bool flag = true;
    for(int i = 1, 【1】; j <= n; j++, i++) {
        if(【2】)
            flag = false; // 不满足要求
    }
    return flag;
}
int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    int l = 【3】, r = n, ans;
    sort(a+1, a+1+n);
    while(l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) {
            【4】;
            ans = mid;
        } else {
            【5】;
        }
    }
    cout << ans << endl;
}

第 1 题（20 分） 1 处应该填的代码是：{{ select(1) }}

• A. j = 1
• B. j = n - mid
• C. j = n - mid + 1
• D. j = mid

第 2 题（20 分） 2 处应该填的代码是：{{ select(2) }}

• A. a[i] - a[j] > k
• B. a[i] - a[j] <= k
• C. a[j] - a[i] > k
• D. a[j] - a[i] <= k

第 3 题（20 分） 3 处应该填的代码是：{{ select(3) }}

• A. 1
• B. 0
• C. n/2
• D. a[1]

第 4 题（20 分） 4 处应该填的代码是：{{ select(4) }}

• A. l = mid
• B. r = mid
• C. l = mid + 1
• D. r = mid - 1

第 5 题（20 分） 5 处应该填的代码是：{{ select(5) }}

• A. l = mid
• B. r = mid
• C. l = mid + 1
• D. r = mid - 1