题解 | #空调遥控#

解法一:滑动窗口

// src:https://ac.nowcoder.com/acm/problem/229310
#include <climits>
#include <complex>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
int n, p, a[N], ans;

int main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];    
    /*
    排序+滑动窗口
    找<=2p大小的窗口
    a[right]表示窗口的最大值(即最大温度),a[left]表示窗口的最小值(即最小温度)
    */ 
    sort(a+1, a+1+n);
    for(int left=1, right=1;right<=n;++right) {
        while(left<=right && a[right]-a[left] > 2*p)
            left++;
        ans=max(right-left+1, ans);
    }
    cout<<ans;
    system("pause");
}

解法二:二分

// src:https://ac.nowcoder.com/acm/problem/229310
#include <climits>
#include <complex>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e6 + 10;
int n, p, a[N], minV = INT_MAX, maxV = INT_MIN, ans;

int SearchStart(int target)
{
    // 查找左端点
    int left = 1, right = n;
    while(left < right)
    {
        int mid = left + (right - left) / 2;
        if(a[mid] < target)
            left = mid+1;
        else if(a[mid] >= target)
            right = mid;
    }
    return left;
}

int SearchEnd(int target)
{
    // 查找右端点
    int left = 0, right = n-1;
    while(left < right)
    {
        int mid = left + (right - left + 1) / 2;
        if(a[mid] <= target)
            left = mid;
        else if(a[mid] > target)
            right = mid-1; 
    } 
    return right;
}

int main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        minV = min(minV, a[i]);
        maxV = max(maxV, a[i]);
    }
    // 排序+二分
    sort(a+1, a+1+n);
    for(int t=minV;t<=maxV;++t) {
        // 找t-p, t+p在a数组中出现的开始位置和结束位置
        int left=SearchStart(t-p);
        int right=SearchEnd(t+p);
        if(left != -1 && right != -1)
            ans=max(right-left+1, ans);
    }
    cout<<ans;
    system("pause");
}