[编程题]Set Similarity (25)-白红宇的个人博客

[编程题]Set Similarity (25)

发布日期：2021-05-07 23:12:07 浏览次数：25 分类：精选文章

本文共 1526 字，大约阅读时间需要 5 分钟。

关键词：set , vector, STL

试题链接：

问题描述：

思路：

这道题很显然是要用集合set来解决的。

C++STL模板中的set（集合）有两个特点：

1.集合中没有重复元素。
2.集合内部是自动有序的。

对于集合求交并补常用的几个函数：

//求v[a] v[b]并集并将结果存放于一个vector u中set_union(v[a - 1].begin(), v[a - 1].end(), v[b - 1].begin(), v[b - 1].end(), inserter(u, u.begin()));//求v[a] v[b]交集并将结果存放于一个vector inter中set_intersection(v[a - 1].begin(), v[a - 1].end(), v[b - 1].begin(), v[b - 1].end(), inserter(inter, inter.begin()));//求v[a] v[b]差集并将结果存放于一个vector d中set_difference(v[a - 1].begin(), v[a - 1].end(), v[b - 1].begin(), v[b - 1].end(), inserter(d, d.begin()));

备注：

这道题思路很简单，但是要注意一下输出格式是要保留小数点后一位小数的。

需要以下操作实现：

#include
   
            cout <
    
     <
     
      << rate << "%" << endl;

解决方案：

#include
   
    #include
    
     #include
     
      #include
      
       #include 
       
        using namespace std;int main() {       int N, M, num, K;    //存放集合的变长数组    vector< set
        
          > v; cin >> N; for (int i = 0; i < N; i++) { cin >> M; set
         
           tmp; for (int j = 0; j < M; j++) { cin >> num; tmp.insert(num); //向集合中插入数 } v.push_back(tmp); } cin >> K; for (int i = 0; i < K; i++) { int a, b; cin >> a >> b; vector< int > u; //存放并集 vector< int > inter; //存放交集 set_union(v[a - 1].begin(), v[a - 1].end(), v[b - 1].begin(), v[b - 1].end(), inserter(u, u.begin())); set_intersection(v[a - 1].begin(), v[a - 1].end(), v[b - 1].begin(), v[b - 1].end(), inserter(inter, inter.begin())); float rate=float(inter.size()) / float(u.size()) * 100; cout <
          
           <
           
            << rate << "%" << endl; } return 0;}

上一篇：[编程题]Are They Equal (25)

下一篇：Pycharm安装Pytorch过程

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章