题解 | #空调遥控#

1. 问题分析

1.1 问题本质

给定 $n$ 个点 $a[i]$ 和一个容差 $p$ ，寻找一个基准值 $K$ （室内温度），使得落在区间 $[K-p, K+p]$ 内的点数量最大化。

1.2 数学转化

不等式 $|a[i] - K| \le p$ 可以转化为： $K - p \le a[i] \le K + p$ 或者等价地，对于每一个确定的 $a[i]$ ，只要 $K$ 落入区间 $[a[i]-p, a[i]+p]$ ，该队员即可进入状态。进一步抽象：在数轴上给定 $n$ 个点，求一个长度为 $2p$ 的闭区间 $[L, R]$ （其中 $R - L = 2p$ ），使其覆盖的点数量最多。

2. 算法策略选择

针对此类“变长窗口覆盖”或“区间点集覆盖”问题，主要有两种主流策略：

方案 A：差分数组与前缀和（空间换时间）

由于 $a[i]$ 的取值范围 $V$ 在 $10^6$ 以内，可以将每个队员的需求看作对温度区间 $[a[i]-p, a[i]+p]$ 的一次“覆盖贡献”。使用差分数组记录每个区间的起始和结束，最后通过一次扫描前缀和求出覆盖数最大的点。

优点：时间复杂度 $O(n + V)$ ，在 $V$ 较小时极快。
缺点：若 $a[i]$ 取值范围极大（如 $10^9$ ），则无法应用；且此题需要处理下标越界（负数温度）。

方案 B：排序 + 双指针（最优算法）

将点集 $a[i]$ 排序后，利用滑动窗口（双指针）维护一个跨度不超过 $2p$ 的区间。

分析：该方案不依赖于 $a[i]$ 的取值范围，仅依赖于 $n$ 的规模。它是解决此类统计覆盖问题的标准范式，具有更好的通用性和内存局部性。
判定：选择 方案 B（排序 + 双指针） 作为主算法。

3. 代码实现

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

int main() {
    ios::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 l = 0;
    int ans = 0;
    for (int r = 0; r < n; r++) {
        while (l <= r && a[r] - a[l] > p * 2) {
            l++;
        }
        ans = max(ans, r - l + 1);
    }

    cout << ans << endl;
}