【二分】计算概率

描述 Description

    小明有n个长度不一的小木棍，这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l，让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l，则小明胜，否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。

输入格式 Input Format

输入包含两行。第一行为两个整数n和l。第二行包含n个整数，分别为n个木棍的长度。

输出格式 Output Format

输出包含一个实数，小明胜出的概率，保留两位小数。

样例输入 Sample Input [ 复制数据]

4 5 1 2 3 4

样例输出 Sample Output [ 复制数据]

0.67

时间限制 Time Limitation

各个测试点1s

注释 Hint

n和l都不超过100000


谁知道这种水题还要卡呢？朴素TLE80了。其实要二分，而且还要用long long。所以因此交了3次。

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using std::upper_bound;
using std::sort;
typedef long long ll;
long a[100010];
long getint()
{
	long rs=0;bool sgn=1;char tmp;
	do tmp = getchar();
	while (!isdigit(tmp)&&tmp-'-');
	if (tmp == '-'){tmp=getchar();sgn=0;}
	do rs=(rs<<3)+(rs<<1)+tmp-'0';
	while (isdigit(tmp=getchar()));
	return sgn?rs:-rs;	
}

int main()
{
	freopen("probability.in","r",stdin);
	freopen("probability.out","w",stdout);

	ll n = getint();
	long l = getint();

	for (long i=1;i<n+1;i++)
	{
		a[i] = getint();
	}
	sort(a+1,a+1+n);
	ll cnt = 0;
	for (long i=1;i<n+1;i++)
	{
		long j = upper_bound(a+1,a+i,l-a[i])-a;
		cnt += j-1;
	}
	
	printf("%.2lf",double(2*cnt)/double(n*n-n));
	return 0;
}