题解

难度：中等难度

知识点：递推 数学逻辑

思路：

本题考察递推公式，
1.本题将n无聊，m为不无聊。总共人数为s=n+m。每次从其中随机选出2个，将这两个数中的不无聊变成无聊，最终将s个人全部变成无聊。

2.假设当S个人中有K个人是不无聊，设平均需要f(K)次操作使得S个人全部变为无聊。每一次操作存在3种可能性：

K个不无聊的人都没有被选中，任然存在K个人处于不无聊。概率为：C(s - k, 2)/C(s, 2)

K个不无聊的人中选中了一个，此步后存在K-1个人处于不无聊。概率为：(s - k) * k / C(s, 2)

K个不无聊的人种选中了2个人，此步后存在K-2个人处于不无聊。概率为： C(k, 2)/C(s, 2)

因此：f(k) = 1 + C(s - k, 2) / C(s, 2) f(k) + (s - k) k / C(s, 2) )f(k - 1 )+ C(k, 2) / C(s, 2) f(k - 2)

【注】其中的1为该步骤需要付出的时间

由于f(0)=0；
由此：f(1):带入上述公式可得：f(1)-[(s-2)/s]f(1)=1 即：f(1)=s/2；

采用递推方式进行：

1.首先f0=0,f1=s/2;
采用for循环 利用公式：f(k) = 1 + C(s - k, 2) / C(s, 2) f(k) + (s - k) k / C(s, 2) )f(k - 1 )+ C(k, 2) / C(s, 2) f(k - 2) ,其中cur表示f(k),f(k-1)=f1,f(k - 2)=f0。
当计算出cur后，f0=f1,f1=cur。
###四舍五入保留一位小数：
例：保留五位小数：

#include <iostream>
#include <iomanip>
using namespace std;
int main(){
    float a;
    cin>>a;
    cout<<fixed<<setprecision(5)<<a;
}

本题完整代码

#include<iostream>
#include <iomanip>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    int s=n+m;
    double f0=0,f1=s/2.0;
    for(int k=2;k<=m;k++){
        double cur = s * (s - 1) / (1.0 * k * (2 * s - k - 1)) + 2 * (s - k) * 1.0 / (2 * s - k - 1) * f1 + (k - 1) * 1.0 / (2 * s - k - 1) * f0;
        f0 = f1;
        f1 = cur;
    } 
    cout<<fixed<<setprecision(1)<<f1<<endl;
    return 0;
}