链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld
题目描述
有nnn个鸡窝排成一排，第iii个鸡窝在数轴上的坐标是xix_ixi，有一只小鸡会随机的在一个鸡窝中出现。小红准备在数轴上放置两个栅栏，如果小鸡出现在两个栅栏中间（包括端点），则将被小红关住。为了方便管理，两个栅栏之间的最大距离不能超过kkk。现在小红希望最大化成功“关鸡”的概率，请你帮小红求出这个概率。
输入描述:
第一行输入两个正整数n,kn,kn,k，代表鸡的数量和栅栏的最远距离。 第二行输入nnn个整数xix_ixi，代表每个鸡的位置。 1≤n≤1051\leq n \leq 10^51≤n≤105 1≤k≤1091 \leq k \leq 10^91≤k≤109 −109≤xi≤109-10^9\leq x_i \leq 10^9−109≤xi≤109
输出描述:
一个浮点数，代表小红成功关鸡的概率。如果你的答案和标准答案的误差不超过10−410^{-4}10−4，则认为你的答案正确。
示例1
输入
复制5 5 2 3 -1 4 9
5 5 2 3 -1 4 9
输出
复制0.8
0.8
说明
小红将两个栅栏放置在 -1 和 4 这两个点，这样有 80% 的概率能成功关鸡。
解题思路
这题我一开始是想着暴力两个指针去找小于等于k的包含数最大的区间，但是这样时间复杂度来到了O（n²），明显是过不了的。比赛结束后本人和同学讨论才知道用双指针写（可能也想到了吧，只是不会写）。双指针直接只需要用一个循环，时间复杂度大大减小，用i（快指针）和j（慢指针）来移动。
我总结了几点用双指针思想的题型
1.往往用暴力能有答案，但是时间一般会超，用到两个循环。
2.数据一般是有单调性的，着点和二分挺像的。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<iomanip>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include <stdlib.h>
using namespace std;
int n, k,a[100005],ans=1;
int main()
{
cin >> n>>k;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
for (int i = 0, j = 0; i < n; i++)
{
if (a[i] - a[j]<=k)
{
ans = max(i - j + 1, ans);
}
else
{
j++;
}
}
cout <<fixed<<setprecision(4)<< double(ans) / n;
}
