集合相似度 PTA set_union(并集),set_intersection(交集),set_difference(差集)

7-9 集合相似度 （25 分) 给定两个整数集合，它们的相似度定义为：Nc /Nt ×100%。其中Nc 是两个集合都有的不相等整数的个数，Nt 是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式： 输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10^4 ），是集合中元素的个数；然后跟M个[0,10 ^9 ]区间内的整数。

之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。

输出格式： 对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例： 3 3 99 87 101 4 87 101 5 87 7 99 101 18 5 135 18 99 2 1 2 1 3 输出样例： 50.00% 33.33%

本题的意思是让求出交集，再除以并集

方法一： set_union(并集),set_intersection(交集),set_difference(差集) set_union(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(ss,ss.begin())); set_intersection(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(ss,ss.begin())); set_difference(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(ss,ss.begin()));

方法二： 也可以自己使用迭代器，遍历一遍这两个集合。 集合都是排好序的 谁小谁的指针加加 相同的话，加过去。直到遇到不同的值 这样遍历一遍就记录下来了并集中有多少人 一共有多少人了。

#include
using namespace std;
int n,m,t,q;
set s[51];
set::iterator it,is;
int a,b;
set ss;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        for(int j=0;j!=m;j++)
        {
            cin>>t;
            s[i].insert(t);
        }
    }

    cin>>q;

    bool flag=0;
    int last = 0;

    for(int i=0;i!=q;i++)
    {
        cin>>a>>b;
        ss.clear();
        set_intersection(s[a].begin(),s[a].end(),s[b].begin(),s[b].end(),inserter(ss,ss.begin()));
        printf("%.2f%%
",(ss.size())*100.0/(s[a].size()+s[b].size()-ss.size()));
    }

    return 0;
}
``````
#include
using namespace std;
int n,m,t,q;
set s[51];
set::iterator it,is;
int a,b;
set ss;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>m;
        for(int j=0;j!=m;j++)
        {
            cin>>t;
            s[i].insert(t);
        }
    }

    cin>>q;

    bool flag=0;
    int last = 0;

    for(int i=0;i!=q;i++)
    {
        cin>>a>>b;
        it = s[a].begin();
        is = s[b].begin();

        int min = (1<<31);
        bool flag=0;//标记当前这个最小值是否出出现过重复 
        int cnt = 0;//记录交际里面人的个数
        int sum = 0;//记录总人数 

        while(it!=s[a].end()||is!=s[b].end())
        {
            if(it!=s[a].end()&&*it==min)    
            {
                it++;
                if(!flag) 
                {
                    cnt++;
                }
                flag=1;
                continue;
            }
            if(is!=s[b].end()&&*is==min)    
            {
                is++;
                if(!flag) 
                {
                    cnt++;
                }
                flag=1;
                continue;
            }
            if(it!=s[a].end())
            {
                if(is!=s[b].end())
                {
                    if(*it<=*is)
                    {
                        min = *it;
                        it++;
                    }
                    else
                    {
                        min = *is;
                        is++;
                    }
                }
                else
                {
                    min = *it;
                    it++;
                }
                flag=0;
            }
            else
            {
                min = *is;
                is++;
                flag=0;
            }
            sum++;
        }
        printf("%.2f%%
",cnt*100.0/sum);
    }

    return 0;
}