小R的并集大小期望计算-蛮力
目录
小R的并集大小期望计算 | 蛮力
问题描述
小R有 n 个集合，她想通过随机选择两个集合，并计算它们的并集，来求出这个并集大小的期望值。每个集合中的元素都是唯一的且互不相同。她需要计算出随机选择两个集合并集大小的期望值，并且要求结果保留两位小数。
保证输入至少有两个集合。
测试样例
样例1：
输入：
n = 2,st = [[1, 2], [1, 3, 5]]输出：
'4.00'
样例2：
输入：
n = 3,st = [[1, 4], [2, 5], [3, 6, 7]]输出：
'4.67'
样例3：
输入：
n = 2,st = [[10, 20, 30], [10, 30, 50, 70]]输出：
'5.00'
题解：
题目不是很难，双重遍历整个数组，选取其中两个，并再次遍历其中数据存入set中，就可方便计算出其个数，然后记录总个数与选取个数，相除即为期望。
但是本题的难点在于，怎么将一个double数据转换成string数据，我也不知道，后来查了才发现一个stringstream的类型，可以通过ss « fixed « d来将double转换成string，并使用setprecision来控制小数位数即可。
代码：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<vector>
#include<unordered_set>
#include<unordered_map>
#include<map>
#include<set>
using namespace std;
typedef long long int ll;
string solution(int n, vector<vector<int>> st) {
set<int> st1;
int sum=0;
int num=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
vector<int> vt1=st[i];
vector<int> vt2=st[j];
for(int k=0;k<vt1.size();k++){
st1.insert(vt1[k]);
}
for(int k=0;k<vt2.size();k++){
st1.insert(vt2[k]);
}
sum+=st1.size();
num++;
vt1.clear();vt2.clear();st1.clear();
}
}
double as=0;
string ans="";
as=sum*1.0/num;
//cout << as << "\n";
stringstream ss;
ss.setf(ios::fixed);
ss << setprecision(2) << as;
//cout << ss.str() << "\n";
return ss.str();
}
int main() {
cout << fixed << setprecision(2) << (solution(2, {{1, 2}, {1, 3, 5}}) == "4.00") << endl;
cout << fixed << setprecision(2) << (solution(3, {{1, 4}, {2, 5}, {3, 6, 7}}) == "4.67") << endl;
cout << fixed << setprecision(2) << (solution(2, {{10, 20, 30}, {10, 30, 50, 70}}) == "5.00") << endl;
return 0;
}