Day8 定向补弱 D-E（重制版·10题）

D：完整阅读程序；E：完整完善程序。共 10 题，每题 2 分。

第一组：排序与滑动区间阅读

---

程序功能

程序求最多能选出多少个数组元素，使所选元素的最大值与最小值之差不超过 $k$。排序后，区间 [l,r] 表示当前满足条件的一段连续有序元素。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    sort(a.begin(), a.end());

    int l = 0, best = 0;
    for (int r = 0; r < n; ++r) {
        while (a[r] - a[l] > k) ++l;
        best = max(best, r - l + 1);
    }
    cout << best;
    return 0;
}

第 1 题

输入 7 3 1 8 4 7 2 6 10 时，程序输出（ {{ select(1) }} ）。

• $3$
• $4$
• $5$
• $6$

---

第 2 题

程序执行过程中，变量 l 可能减小（ {{ input(2) }} ）。

---

第 3 题

程序的总体时间复杂度是（ {{ select(3) }} ）。

• $O(n)$
• $O(n^2)$
• $O(n\log n)$
• $O(2^n)$

---

第 4 题

若删去 while 循环，最可能造成（ {{ select(4) }} ）。

• 程序无法读入
• 排序失效
• 答案一定变为 0
• 不再保证所选区间的极差不超过 $k$

---

第 5 题

表达式 r-l+1 表示（ {{ select(5) }} ）。

• 当前合法区间中的元素个数
• 数组不同元素个数
• 被删除元素个数
• 当前区间元素之和

---

第二组：第一个不小于 x 的位置

---

程序功能

给定一个长度为 $n$ 的非降序整数数组 a 和整数 $x$。程序输出第一个满足 a[i]>=x 的下标；若不存在则输出 -1。搜索区间采用左闭右开形式 [l,r)。试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> a(n);
    for (int &v : a) cin >> v;

    int l = 0, r = n;
    while (l < r) {
        int mid = ____①____;
        if (a[mid] < x)
            l = ____②____;
        else
            ____③____;
    }
    if (____④____) cout << l;
    else cout << ____⑤____;
    return 0;
}

第 6 题

①处应填（ {{ select(6) }} ）。

• l+r
• (l+r)/2
• (l+r+1)/2
• r-l

---

第 7 题

②处应填（ {{ select(7) }} ）。

• mid
• r-1
• l+1
• mid+1

---

第 8 题

③处应填（ {{ select(8) }} ）。

• l=mid+1
• r=mid-1
• r=mid
• l=mid

---

第 9 题

④处应填（ {{ select(9) }} ）。

• l==0
• l<n && a[l]>=x
• a[l]<x
• r==n

---

第 10 题

⑤处应填（ {{ select(10) }} ）。

• -1
• 0
• n
• x

---