题目描述
小明有n个长度不一的小木棍,这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l,让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l,则小明胜,否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。
输入
输入包含两行。第一行为两个整数n和l,其中n和l都不超过100000。第二行包含n个整数,分别为n个木棍的长度。
输出
输出包含一个实数,小明胜出的概率,保留两位小数。
样例输入
4 5 1 2 3 4
样例输出
0.67
提示
代码
#include<bits/stdc++.h> using namespace std; const int N=100001; long long n,t,a[N],l,r,mid,sum; long long ans,tmp; int main() { scanf("%lld%lld",&n,&t); tmp=n*(n-1); for(int i=1;i<=n;i++) scanf("%lld",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) { l=1,r=n,sum=0; while(l<=r) { mid=(l+r)/2; if(a[i]+a[mid]<=t) l=mid+1,sum=mid; else r=mid-1; } if(sum>=i) sum--; ans+=sum; } printf("%.2lf",(double)ans/tmp); return 0; }
原文链接: https://www.cnblogs.com/LJA001162/p/13124905.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/355052
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!