Marbles Lucky Distribution Gym - 101845M --概率、思维、贪心

题目链接

题目描述
胡安有N个红色弹珠,M个蓝色弹珠,和K个瓶子。他将在K个瓶子中的每个瓶子上放一定数量的弹珠,使得没有瓶子是空的,每个弹珠都在瓶子里。

安德烈是一个圣菲球迷,所以他将以均匀分布的方式随机挑选一个瓶子,然后他将以均匀分布的方式随机挑选瓶子里的弹珠,希望是一个红色弹珠。由于胡安是Millonarios的球迷,他想把瓶子里的弹珠分配到安德烈选到蓝色弹珠的概率最大。胡安的生活很忙碌,因此他需要你的帮助来确定弹珠的最佳排列方式和安德烈得到蓝色弹珠的概率。

Input
输入由三个用空格隔开的整数N M和K(1≤N, M, K≤ 1 0 9 10^{9} 109)-分别是红弹珠、蓝弹珠和瓶子的数量。

Output

打印Bob得到蓝色弹珠的概率,使弹珠排列最优。你的答案将被认为是正确的,如果它的绝对或相对误差不超过 1 0 − 6 10^{-6} 10−6。

Sample Input
50 50 2

Sample Output
0.747474747

题目分析

在每个瓶子里放1个蓝球,如果有剩余的蓝球,就把所有剩余的蓝球放在瓶子1里。
如果还有空瓶子,就把所有红色的瓶子分到空瓶子里。否则,将所有红色的放在1号瓶中。 计算得到蓝色的概率。
一个瓶子里只有蓝球拿到的概率必定是100%,贪心。

#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int inf = 0x3f3f3f3f;
const int N = 5e4 + 7;

signed main() {
    double n, m, k;
    cin >> n >> m >> k;
    double ans;
    if (k > m)
        ans = m / k;
    else
        ans = (k - 1) / k + (m - k + 1) / (n + m - k + 1) / k;
    printf("%.7f", ans);
    return 0;
}
上一篇:[CF1215E] Marbles - 状压dp


下一篇:[ARC086E]Smuggling Marbles(树形dp+启发式合并)