题解 | #小红关鸡#

问题分析

本问题的核心是在一维数轴上寻找一个长度不超过 $k$ 的闭区间 $[L, R]$ ，使得该区间内覆盖的离散点（鸡窝）数量最大化。

概率本质：由于小鸡等概率出现在 $n$ 个鸡窝中，成功“关鸡”的概率 $P = \frac{m}{n}$ ，其中 $m$ 是落在区间 $[L, R]$ 内的鸡窝数量。由于 $n$ 是常数，最大化概率等价于最大化 $m$ 。
区间边界确定性：对于任意一个包含 $m$ 个点的最优区间 $[L, R]$ ，我们总可以通过平移该区间，使得区间的左端点 $L$ 与该区间内最左侧的鸡窝坐标 $x_i$ 重合，且不减少区间内点的数量。因此，搜索空间可以缩减为：以每个鸡窝坐标 $x_i$ 作为左端点，寻找最大的下标 $j$ 使得 $x_j - x_i \leq k$ 。
数据规模：
- $n = 10^5$ ：要求算法复杂度至少达到 $O(n \log n)$ 或 $O(n)$ 。
- 坐标 $x_i$ 及距离 $k$ 达到 $10^9$ ：必须考虑坐标的离散性，不能建立基于坐标值的数组，且计算差值时需注意数值范围。

算法：滑动窗口 (Sliding Window)

针对该模型，排序结合双指针（滑动窗口） 是最优的算法策略。

虽然可以通过对每个点进行二分查找（Binary Search）来确定右边界，从而实现 $O(n \log n)$ 的复杂度。但滑动窗口利用了坐标的单调性，可以将搜索过程优化至线性 $O(n)$ 。结合预处理的排序，整体性能达到最优。

预处理：首先对原始坐标数组 $X$ 进行升序排序。排序后，若 $j > i$ ，则必有 $x_j \geq x_i$ 。
窗口定义：维护一个左指针 left 和右指针 right，代表当前考虑的候选区间范围。
单调性维护：
- 随着 right 指针向右移动，区间长度 $x_{right} - x_{left}$ 单调递增。
- 当当前区间长度超过 $k$ 时，必须向右移动 left 指针以收缩区间，直到重新满足 $x_{right} - x_{left} \leq k$ 。
全局最优解：在 right 遍历过程中，记录窗口内元素个数 right - left + 1 的历史最大值。

复杂度分析

1. 时间复杂度

排序阶段：使用快速排序或归并排序，复杂度为 $O(n \log n)$ 。
滑动窗口阶段：left 和 right 指针各遍历数组一次，复杂度为 $O(n)$ 。
总复杂度： $O(n \log n)$ 。

2. 空间复杂度

辅助空间：除了存储输入坐标的数组外，仅需常数级别的额外变量。
总复杂度： $O(n)$ (取决于排序实现及输入存储)。

代码实现

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

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

    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    for (int i = 0; i < n; i++)
        cin >> x[i];

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

    int l = 0;
    int r = 0;
    int most = 0;
    while (r < n) {
        while (l <= r && x[r] - x[l] > k) {
            l++;
        }

        most = max(most, r - l + 1);
        r++;
    }

    double p = 1.0 * most / n;
    cout << fixed << setprecision(8) << p << endl;
}