首页 > 代码库 > Codeforces 107B Basketball Team 简单概率

Codeforces 107B Basketball Team 简单概率

题目链接:点击打开链接

题意:

给定n m h

表示有m个部门,有个人现在在部门h

下面m个数字表示每个部门的人数。(包括他自己)

在这些人中随机挑选n个人,问挑出的人中存在和这个人同部门的概率是多少。

这个人一定在挑出的n个人中。

反向思考。答案是 1 - 不可能概率

不可能概率 = C(n-1, sum-1-a[h]) / C(n-1, sum-1)

发现2个组合数的分母部分相同,所以只需要把2个组合数的分子部分相除即可。


#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <map>
#include <set>
using namespace std;
#define N 10010
int n, m, h, a[N];

void solve(){
    int sum = 0;
    for(int i = 1; i <= m; i++) scanf("%d",&a[i]), sum += a[i];
    if(sum < n){
        puts("-1");return ;
    }
    n--;
    sum--; a[h]--;
    if(sum - a[h] < n){puts("1");return;}
    double ans = 1.0;
    double x = sum-a[h], y = sum;
    for(int i = 1; i <= n; i++) {
        ans *= x / y;
        x--; y--;
    }
    printf("%.10f\n", 1.0 - ans);
}
int main(){
    while(~scanf("%d %d %d",&n,&m,&h)){
        solve();
    }
    return 0;
}


Codeforces 107B Basketball Team 简单概率