HDU 4503 湫湫系列故事——植树节

湫湫系列故事——植树节

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 694 Accepted Submission(s): 409

Problem Description

　　今天是一年一度的植树节，腾讯幼儿园要求每个老师在班里选出几个小朋友一起去野外种植小树苗，根据学校的整体安排，湫湫老师的班里要选出3个小朋友。已知湫湫的班里共有n个孩子，每个孩子有Bi个朋友(i从1到n)，且朋友关系是相互的，如果a小朋友和b小朋友是朋友，那么b小朋友和a小朋友也一定是好朋友。为了选择的公平性，湫湫老师会随机抽取3个小朋友出来(每个人被抽到的概率相同)，但是她很希望这3个小朋友之间的关系完全相同，湫湫老师想请你帮她算算抽到的3个小朋友正好关系相同的概率是多少？
　　PS. 关系相同就是指要么3个人互相是好朋友，要么3个人互相都不是好朋友。

Input

输入数据第一行是一个整数T(1<=T<=1000)，表示输入数据的组数；每组数据的第一行是一正整数n表示孩子的总数(2<n<=1000)，第二行有n个数Bi (i从1到n)，分别代表每个小朋友的朋友的个数。

Output

对于每组数据，请输出抽到的3个小朋友关系相同的概率，结果保留3位小数。

Sample Input

1 5 3 3 3 3 4

Sample Output

0.400

Source

2013腾讯编程马拉松初赛第〇场（3月20日）

Recommend

liuyiding

有n个孩子

每个孩子有 b[i]个朋友自然有 n-1-b[i]个非朋友他自己，他的一个朋友，他的一个非朋友构成的组合是不满足题意的

但是除此之外的所有组合都满足题意

故可以通过计算不满足的组合

对每个孩子有b[i]*(n-1-b[i])个组合，这个组合累加会被他的朋友再计算一次，所以结果除以2就是不满足的组合数

总的组合是C（n，3）

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

int n,num[1010];

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&num[i]);
            ans+=1*num[i]*(n-1-num[i]);
        }
        ans/=2;
        printf("%.3f\n",1.0-ans*1.0/((n*(n-1)*(n-2))/6));
    }
    return 0;
}