Note: This article is available in Chinese only. 本文暂无英文版本。
View original
http://codeforces.com/problemset/problem/107/B
题意：有m个部门，每个部分s[i]个人，HW在第h部门，现在要从这m个部门中挑选包括HW在内的n个人去参加比赛，问被挑选的人中有HW的队友（同部门的人）的概率是多少。如果m个部分的人数不够组成n人的球队，输出-1.#
思路：考虑一般情况。至少有一个队友的情况较多，应该从反面考虑，即没有一个队友的情况。选完HW以后面临的状态是：事件总数为从total(m个部门的人员之和)-1个人中选n-1个的方案数，包含的事件数目为从a(a=total-s[h])中选n-1个人包含的方案数。 可以看出分母相同，可以约掉。#
然后对于边界情况，首先判断total是否比n小。然后，如果a<n-1,表示除去HW所在的h部分之外的人不可能组成n-1个人，也就是一定要选择HW的队友，概率为1.
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月03日 星期三 17时56分30秒
4File Name :code/cf/problem/107B.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int M=1E3+7;
34int n ,m,h;
35int s[M];
36int main()
37{
38 #ifndef ONLINE_JUDGE
39 freopen("code/in.txt","r",stdin);
40 #endif
41
42 cin>>n>>m>>h;
43 for ( int i = 1 ; i <= m ; i++) cin>>s[i];
44
45 double total = 0;
46 for ( int i =1 ; i <= m ; i++)
47 {
48 total+=s[i];
49 }
50 if (total<n)
51 {
52 puts("-1");
53 return 0;
54 }
55 total--;
56 n--;
57 s[h]--; //减去那个人。
58 double a = total - s[h];
59 double ans = 1.0;
60// cout<<"total:"<<total<<" a:"<<a<<endl;
61 if (a<n) //s[h]队外的人无法满足剩余的要求。
62 {
63 puts("1");
64 return 0;
65 }
66 for ( int i = 1 ; i <= n ; i++)
67 {
68 ans = ans *(a*1.0/total*1.0);
69// cout<<"ans:"<<ans<<endl;
70 a--;
71 total--;
72 }
73 printf("%.10f",1-ans);
74
75 #ifndef ONLINE_JUDGE
76 fclose(stdin);
77 #endif
78 return 0;
79}