Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
小明有n个长度不一的小木棍，这些木棍的长度都是正整数。小明的父亲想和小明做一个游戏。他规定一个整数长度l，让小明闭着眼睛从n个木棍中随便拿出两个。如果两个木棍的长度总和小于等于l，则小明胜，否则小明的父亲胜。小明想知道他胜出的概率究竟有多大。【输入格式】
输入包含两行。第一行为两个整数n和l，其中n和l都不超过100000。第二行包含n个整数，分别为n个木棍的长度。
【输出格式】
输出包含一个实数，小明胜出的概率，保留两位小数。
Sample Input
4 5 1 2 3 4
Sample Output
0.67
【题解】
输入的数据有一些是没有用的。
比如出现了一个数字大于等于l。
则无论它和另外哪一种木棍组合都没办法组合出小于等于l的。
所以可以舍弃掉。
对于那些小于l的木棍。
开一个数组num[1..l]记录它们的个数。
然后用s累加前j种数字的总个数。
然后k=l-j;
对于j∈1..l/2;
ans+= s*num[k];
注意s会随j的累加逐渐变大。
这是因为k可以和j累加变成l正好。也可以和小于j的数字组合成小于l的长度。
最后累加的s还有用。
ans+=C(s,2)；
设两根木棒长度为x1,x2;
我们处理的第一种情况是x1<l/2<x2;
然后C(s,2)则表示x1<x2<=l/2;
可以预见x1,x2不能同时大于l/2;
然后n要用__int64类，不然n*(n-1)的时候可能会溢出。
不区别组合出的长度小于等于l的情况的总数是C(n,2);
所以最后求概率的时候除C(n,2)即可。
C(n,2)=n*(n-1)/2;
【代码】
/*
输入的数据有一些是没有用的。
比如出现了一个数字大于等于l。
则无论它和另外哪一种木棍组合都没办法组合出小于等于l的。
所以可以舍弃掉。
对于那些小于l的木棍。
开一个数组num[1..l]记录它们的个数。
然后用s累加前j种数字的总个数。
然后k=l-j;
对于j∈1..l/2;
ans+= s*num[k];
注意s会随j的累加逐渐变大。
这是因为k可以和j累加变成l正好。也可以和小于j的数字组合成小于l的长度。
最后累加的s还有用。
ans+=C(s,2)；
设两根木棒长度为x1,x2;
我们处理的第一种情况是x1<l/2<x2;
然后C(s,2)则表示x1<x2<=l/2;
可以预见x1,x2不能同时大于l/2;
*/
#include <cstdio>
int num[100001] = { 0 };//记录长度小于l的木棍各有多少根。
__int64 n, l;//用__int64.防止溢出
void input_data();
void get_ans();
int main()
{
input_data();
get_ans();
return 0;
}
void get_ans()
{
int j = 1, k = l - 1;//j+k==l始终成立
double s =0, ans = 0;
while (k > j)//如果k是大于j的。
{
s += num[j];//累加前j种数字的总个数。
ans += num[k] * s;//k可以和1..j组合成小于等于l的长度
k--;//一直往中间靠。
j++;//直到k<=l/2为止
}
if (k == j) //k==j的情况 比如j=1,然后l=4.则l-1等于3.j++,k--后j==2；
s += num[j];//而2<=l/2所以归为第二类。即C(S,2);
ans += s*(s - 1)/2.0;//获取第二类的方案数
ans = ans / (n*(n - 1) / 2.0);//总数是C(n,2);
printf("%.2lf", ans);//保留两位输出。
}
void input_data()
{
scanf("%I64d%I64d", &n, &l);
for (int i = 1; i <= n; i++)//输入n个数字
{
int x;
scanf("%d", &x);//记录长度小于l的木棍x的个数。
if (x < l)
num[x]++;
}
}