首页 > ACM题库 > HDU-杭电 > HDU 4503-湫湫系列故事――植树节-概率-[解题报告]HOJ
2015
07-17

HDU 4503-湫湫系列故事――植树节-概率-[解题报告]HOJ

湫湫系列故事――植树节

问题描述 :

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

输入:

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

输出:

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

样例输入:

1
5
3 3 3 3 4

样例输出:

0.400

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        int i,j,k,s=0,a;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a);
            s+=a*(n-1-a);
        }
        int t=n*(n-1)*(n-2)/6;//C(n,3)
        printf("%.3lf\n",1-1.0*s/2/t);
    }
    return 0;
}
/*
    要求符合要求的概率,可以先求不符合的
    不符合就是,一个人a,与b是朋友,与c不是朋友,b和c随意
    则对于第i个人,其可能的朋友组合有ai*(n-ai-1),其中有重复的。
    取重复:由于选定的是一个人,对于上述a,b,c,重复的就是讨论选a,b,c三种时的重复关系
    上述(=为是朋友,!=为不是朋友)a=b,a!=c,b?c
    若b=c,选定人是b时不可以,因为b=a,b=c不符合;选定人是c时可以,c!=a,c=b符合
    若b!=c,选定人是b时可以,因为b=a,b!=c符合;选定人是c时不可以,c!=a,c!=b不符合
    综上可知,重复了一次,总数/2就是不符合的结果
*/

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/10048519