仓库（warehouse）

解题思路

仓库必须位于某个村庄，所以不能只找长度2D的任意区间。先把村庄坐标排序，然后对每个现有村庄x[i]作为仓库，求闭区间[x[i]-D,x[i]+D]内的村庄数。

仓库从左向右移动时，覆盖区间左右端都不下降。用左指针left跳过太远的左边村庄，右指针right推进到第一个超过右边界的位置，覆盖数为right-left。每个指针全程最多走n次。

正确性说明

每个合法仓库位置都被枚举。双指针维护的恰是当前仓库距离≤D的全部村庄，故每次计数准确；对所有允许仓库位置取最大得到全局最优。

易错点

中心必须是输入村庄，不是任意实数点；距离正好D的村庄也被覆盖；D=0时因坐标互异答案1。

复杂度

排序O(n log n)，扫描O(n)，空间O(n)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long D;
    cin >> n >> D;
    vector<long long> x(n);
    for (auto &v : x)
        cin >> v;
    sort(x.begin(), x.end());
    int left = 0, right = 0, answer = 0;
    for (int i = 0; i < n; i++) {
        while (left < n && x[left] < x[i] - D)
            left++;
        while (right < n && x[right] <= x[i] + D)
            right++;
        answer = max(answer, right - left);
    }
    cout << answer << "\n";
    return 0;
}