小明木棍
时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte
总提交:1746 测试通过:45
描述
小明有n个长度不一的小木棍，这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l，让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l，则小明胜，否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。
输入
输入包含两行。第一行为两个整数n和l，其中n和l都不超过100000。第二行包含n个整数，分别为n个木棍的长度。
输出
输出包含一个实数，小明胜出的概率，保留两位小数。
样例输入
4 5
1 2 3 4
样例输出
0.67
提示
题目来源
NUAA
分析：这道题比较恶心，感觉，因为其实题意并不难理解，不过用到了快速排序和变形的二分查找。未完待续。
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
int a[3]={0},b[MAXN]={0};
int counts=0,l;
int Comp(const void *p1,const void *p2 )
{
return *((int *)p1) - *((int *)p2);
}
int binsrch( int n,int k){
int low,high,mid,s=-1;
low=0;high=n;
if (k<b[0])
{
return 0;
}else if (k>b[n-1])
{
return n-1;
}
while (low<=high){
mid=(low+high)/2;
if (k>b[mid])
{
low=mid+1;
if (b[low]>k)
{
return low-1;
}
}
else if (k<b[mid])
{
high=mid-1;
if (b[high]<k)
{
return high;
}
}
else if (k==b[mid])
{
return mid;
}
}
}
int main()
{
int m,r,i,j;
float q;
scanf("%d",&m);
scanf("%d",&l);
for (i=0;i<m;i++)
{
scanf("%d",&b[i]);
}
qsort(b,m,sizeof(int),Comp);
for (i=0;i<m-1;i++)
{
j=binsrch(m,l-b[i]);
if (i>=j)
{
break;
}
else
{
counts+=j-i;
}
}
printf("%.2f\n",(float)counts*2/m/(m-1));
}