空调遥控

题目链接： https://ac.nowcoder.com/acm/problem/229310

这道题目看起来不好解决，其实我们只需要转换一下思路：

将我们需要求解的问题：输出一个数字，表示最多有多少队员同时进入训练状态 -> 「在排序数组中寻找最长连续子数组，使子数组中最大元素与最小元素的差不超过 2p」

采用 排序 + 双指针 策略，时间复杂度为 O(n log n)（主要来自排序），空间复杂度为 O(1)（忽略排序所需空间）。

#include <iostream>
#include <vector>
#include <algorithm>  // 包含sort排序函数
using namespace std;

int main()
{
    int n, p;  // n：数组长度；p：题目给定参数，用于计算允许的最大差值（2*p）
    cin >> n >> p;  // 读取n和p
    vector<int> nums(n);  // 存储输入的数组
    for(int i = 0; i < n; i++)
        cin >> nums[i];  // 读取数组元素
    
    // 关键：先对数组排序。排序后，子数组的最小元素是nums[l]，最大元素是nums[r]（因数组升序）
    sort(nums.begin(), nums.end());
    
    int ret = 0;  // 记录最长有效子数组的长度（结果）
    int l = 0, r = 0;  // 双指针：l是左边界，r是右边界，维护区间[l, r]
    
    // 右指针r从0遍历到n-1，扩展区间右边界
    while(r < n)
    {
        // 若当前区间的最大-最小 > 2p，说明区间无效，移动左指针l缩小范围
        // 直到区间有效（nums[r] - nums[l] ≤ 2p）
        while(nums[r] - nums[l] > 2 * p) 
            l++;  // 左指针右移，缩小区间
        
        // 此时[l, r]是有效区间，计算长度（r-l+1），更新最长长度ret
        ret = max(ret, r - l + 1);
        
        r++;  // 右指针右移，尝试扩展区间
    }
    
    // 输出最长有效子数组的长度
    cout << ret << endl;
    return 0;
}