小红关鸡【牛客tracker 每日一题】

小红关鸡时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述有n nn个鸡窝排成一排第i ii个鸡窝在数轴上的坐标是x i x_ixi​有一只小鸡会随机的在一个鸡窝中出现。小红准备在数轴上放置两个栅栏如果小鸡出现在两个栅栏中间包括端点则将被小红关住。为了方便管理两个栅栏之间的最大距离不能超过k kk。现在小红希望最大化成功“关鸡”的概率请你帮小红求出这个概率。输入描述第一行输入两个正整数n , k n,kn,k代表鸡窝的数量和栅栏的最远距离。第二行输入n nn个整数x i x_ixi​​代表每个鸡窝的位置。1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤1051 ≤ k ≤ 10 9 1≤k≤10^91≤k≤109、− 10 9 ≤ x i ≤ 10 9 −10^9≤x_i≤10^9−109≤xi​≤109输出描述一个浮点数代表小红成功关鸡的概率。如果你的答案和标准答案的误差不超过10 − 4 10^{−4}10−4则认为你的答案正确。示例1输入5 5 2 3 -1 4 9输出0.8说明小红将两个栅栏放置在− 1 -1−1和4 44这两个点这样有80 % 80\%80%的概率能成功关鸡。解题思路本题核心是排序二分查找求解长度不超过k的区间内最多鸡窝数量。由于鸡窝坐标无序首先对坐标数组进行升序排序利用有序数组的连续性优化查找。枚举每个鸡窝作为区间左端点通过upper_bound快速找到右侧最远的、坐标不超过左端点 k kk的鸡窝位置计算该区间内的鸡窝数量遍历所有左端点后得到最大覆盖数量。最终成功关鸡的概率为最大覆盖数量 / 总鸡窝数n按要求输出保留六位小数的结果。算法时间复杂度为O ( n log ⁡ n ) O(n\log n)O(nlogn)完美适配n ≤ 10 5 n≤10^5n≤105的大数据规模。总结核心逻辑排序鸡窝坐标用二分查找找到长度≤k的最大覆盖鸡窝数计算概率。关键操作数组排序、二分定位右端点、统计最大区间数量、浮点概率计算。效率保障O ( n log ⁡ n ) O(n\log n)O(nlogn)复杂度高效处理大规模数据满足时间与精度要求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N2e510;constll INF1e18;constll M1e610;intmain(){ll n,k;cinnk;vectorlla(n);for(ll i0;in;i)cina[i];sort(a.begin(),a.end());ll ans0;for(autoia.begin();i!a.end();i){autoitupper_bound(a.begin(),a.end(),*ik);ansmax(ans,ll(it-i));}printf(%.6f,ans*1.0/n);return0;}