思路如下:
由于「相似度 = 共有元素 / 所有元素」
我的思路是「共有元素 = 两集合所有元素 - 两集合不重复元素」,比如集合一 {87, 99 , 101},集合二去重后 {5, 87, 101} 共 6 个元素,而两集合不重复元素 {5, 87, 99, 101} 共 4 个元素,那么这两个集合共有元素就是 2 个
顺着这个思路非常暴力地写出了第一个算法:
/* 伪码 */ 1. 输入:由于一开始不知道要计算哪两个集合,所以先将所有输入数据另行保存 2. 处理: 1) 根据集合对,选出相应两集合,遍历集合1,枚举每个元素并加入 set1 和 set_total;再遍历集合2,枚举每个元素加入 set2 和 set_total 2) 计算共有元素 = (set1.size() + set2.size()) - set_total.size(); 3) 计算相似度 = 共有元素 / set_total.size()
#include <cstdio> #include <vector> #include <set> using namespace std; static const int maxn = 50; static const int maxm = 2000; vector<vector<int> > set_dat(maxn);//set data vector<vector<int> > set_pai(maxm);//set pair int main() { set<int> set_tot;//set total set<int> set_1, set_2; int n, k, m; //1. INPUT scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", &k); for (int j = 0; j < k; ++j) { int inp; scanf("%d", &inp); set_dat[i].push_back(inp); } } scanf("%d", &m); for (int i = 0; i < m; ++i) { for (int j = 0; j < 2; ++j) { int inp; scanf("%d", &inp); set_pai[i].push_back(inp); } } //2. EXECUTE for (int i = 0; i < m; ++i) { int set_idx_1, set_idx_2; set_idx_1 = set_pai[i][0] - 1; set_idx_2 = set_pai[i][1] - 1; set_1.clear(); set_2.clear(); set_tot.clear(); for (int j = 0; j < set_dat[set_idx_1].size(); ++j) {//traversal first set set_1.insert(set_dat[set_idx_1][j]); set_tot.insert(set_dat[set_idx_1][j]); } for (int j = 0; j < set_dat[set_idx_2].size(); ++j) {//traversal second set set_2.insert(set_dat[set_idx_2][j]); set_tot.insert(set_dat[set_idx_2][j]); } double Nc, Nt; Nc = (set_1.size() + set_2.size()) - set_tot.size(); Nt = set_tot.size(); printf("%.1lf%%\n", Nc / Nt * 100); } return 0; }第一次暴力解完整代码
后来最后一个测试点超时,看了晴神解析发现能优化的地方有两处:
1. 我一开始是先将所有输入保存到 vector,然后再遍历 vector 将元素加入 set,那不如直接一步到位将所有输入保存到 set
2. 题意所求共有元素 Nc、不重复元素 Nt,实际就是求交集并集,而这个求交集并集有一个更快的方法是:
2-1. 求并集:直接将并集元素初始为另一集合 y 元素个数,这样只需遍历一个集合 x 便可得到结果——集合 x 当前元素在集合 y 不存在,并集元素加一
2-2. 求交集:将交集元素初始为零,这样也是只需遍历一个集合 x 便可得到结果——集合 x 当前元素在集合 y 存在,交集元素加一
修改代码后提交便 A 了