[排序/二分查找]| #小红关鸡#

想要得到最大的概率，实际上就是找出某个端点 到 所能覆盖的最多鸡窝数，显然端点应该贪心的为其中一个鸡窝，我们只要从一个鸡窝 出发，判断最大能包含的鸡窝数，记录其中的最大值除以 即可。排序后，使用二分查找到大于 的位置，减去 就得到了该区间包含的鸡窝数。

#include <iostream>
#include<algorithm>
using namespace std;

const int N = 1e5+10;
int a[N];

int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a,a+n);
    int ans = 0;
    for(int i=0;i<n;i++){
        int p = a[i]+k;
        int j = upper_bound(a,a+n,p)-a;
        ans = max(j-i,ans);
    }
    double pb = ans/(double)n;
    cout << pb;
}