题意简述
有一张 \(n\) 个节点的无边图,图在连通之前每次随机抽取一个点然后建边,求期望操作次数(即最大多少次)。
思路
这道题似乎和图论没什么关系,首先我们看 \(n\) 个球抽出一个的概率是 \(\frac{1}{n}\) ,那么抽第二个时概率是 \(\frac{1}{n-1}\) 以此类推。所以最坏情况下就是抽第 \(n-1\) 个球是都没有抽到,所以我们就只需要把 \(1\) 到 \(n-1\) 每个球抽中的概率加起来就行了。
code
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
double ans=0.0;
for(double i=1;i<n;i++) ans+=(double)n/(n-i);
cout<<fixed<<setprecision(10)<<ans<<endl;
return 0;
}
标签:frac,int,题解,abc194,Journey,ABC194D
From: https://www.cnblogs.com/wenzhihao2023/p/18069260