题目分析：寻找满足题意的最大子区间

【牛客：空调遥控】

题目链接：https://www.nowcoder.com/practice/7cb58d56b30c4280ac07ae4428022e03

知识点：双指针、二分

输入：6 2
      1 5 3 2 4 6

输出：5

说明：温度调成3或4，都可以满足5名队员同时进入训练状态

---

当看见这一题后，可能会直接使用暴力枚举的方法。

暴力枚举写法

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

bool Satisfy(int i, int k, int p){
    if(abs(i-k)<=p){
        return true;
    }
    return false;
}

int main() {
    int n,p;
    cin>>n>>p;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin>>a[i];
    }

    sort(a.begin(),a.end());

    int best = 0;
    for(int k=a[0]; k<=a[n-1]; k++){
        int count = 0;
        for(int x:a){
            if(Satisfy(x,k,p)){
                count++;
            }
        }
        best = max(best,count);
    }
    cout<<best;
}

但是由于数据量过大，暴力枚举的时间复杂度为 O(n²)，在数据量过大时会导致 TLE，所以需要对现有代码进行优化。

---

题目分析

原命题：存在一个实数中心 k，使得对于子数组中的任意元素 x，都满足：k - p <= x <= k + p

易得转化命题：对于子数组中的最小值 min_val 和最大值 max_val，满足：max_val - min_val <= 2 * p

所以就可以转化为求序列中满足条件的最大子序列。

所以，可以使用双指针写法，寻找到满足 max_val - min_val <= 2 * p 的最大子序列，然后求得其中元素个数即可。

双指针/滑动窗口写法

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,p;
    cin>>n>>p;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    sort(a.begin(),a.end());

    int best = 0;
    for(int right=0 ,left=0; right<n; right++){   // 让右指针 i 从 0 遍历到 n-1

        while(left<=right && (a[right] - a[left]) > p*2){     //while 循环：收缩左边界
            // 如果窗口不合法，就将左指针 left 向右移动一位，缩小窗口
            left++;
        }
        //此时，窗口 [left, right] 是以 right 为右边界的、满足条件的最长合法窗口
        best = max(best, right-left+1);
    }
    cout<<best;
}

使用双指针，时间复杂度为 O(n log n)，满足题目要求。

---

二分写法

当然，使用二分法也可以快速寻找到最大子序列。

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, p;
    cin >> n >> p;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a.begin(), a.end());

    int best = 0;
    for (int i = 0; i < n; i++) {
        // 计算右边界最大允许值
        int right_limit = a[i] + 2 * p;

        // 使用 upper_bound 找到第一个大于 right_limit 的位置
        auto it = upper_bound(a.begin(), a.end(), right_limit);

        // 第四步：计算当前窗口的长度
        // [a.begin() + i, it) 这个区间内的所有元素都满足条件
        // 元素个数 = it - (a.begin() + i) = (it - a.begin()) - i
        int current_count = (int)(it - a.begin()) - i;

        // 第五步：更新全局最大值
        best = max(best, current_count);

    }
    cout << best;
}

时间复杂度同样为 O(n log n)，满足题目要求。

---

总结

综上所述，面对有序的序列时，可以考虑使用双指针或二分进行优化。