1063. Set Similarity (25)

题目例如以下：

Given two sets of integers, the similarity of the sets is defined to be N_c/N_t*100%, where N_c is the number of distinct common numbers shared by the two sets, and N_t is the total number of distinct numbers in the two sets. Your job is to calculate the similarity of any given pair of sets.

Input Specification:

Each input file contains one test case. Each case first gives a positive integer N (<=50) which is the total number of sets. Then N lines follow, each gives a set with a positive M (<=10⁴) and followed by M integers in the range [0, 10⁹]. After the input of sets, a positive integer K (<=2000) is given, followed by K lines of queries. Each query gives a pair of set numbers (the sets are numbered from 1 to N). All the numbers in a line are separated by a space.

Output Specification:

For each query, print in one line the similarity of the sets, in the percentage form accurate up to 1 decimal place.

Sample Input:

3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3

Sample Output:

50.0%
33.3%

这道题目要求从两个集合中不反复的找到公共部分Nc和全部不反复元素Nt，然后计算Nc占Nt的比例。

假设使用多个map进行查询，题目非常easy完毕，可是这道题对于滥用map进行了限制。我最初使用多个map。查找方式找出公共部分和所有不反复元素时最后一个case出现了超时，后来换了一个思路。

仅仅使用一个map，用于过滤在一个集合输入过程中反复的元素，这样得到的每一个集合元素都是不同的，然后把每一个集合元素依照升序排序。最后比較时就能够不同map了。我们使用两个指针curA、curB分别代表遍历到的集合A、集合B的位置。

初始化Nc = Nt = 0，依照以下的操作进行：

cur的移动原则：谁小移动谁去跟大的接近。

①检查curA和curB是否越界，越界则跳到③。

②假设setA[curA] > setB[curB]，此时应该移动curB，依据移动原则。在curB移动过程中。全部遇到的setB[curB]元素均为setA中所没有的，此时Nt++；假设setA[curA] == setB[curB]，说明碰到了公共元素，此时Nc++。Nt++（注意公共元素也算作不同元素中的一个），而且curA和curB均移动；假设setA < setB[curB]，此时应该移动curA。依据移动原则，全部遇到的setA[curA]元素均为setB所没有的，此时Nt++。

③检查setA和setB是否有没遍历完的，假设有，说明剩下的都应该属于Nt。

代码例如以下：

#include <iostream>
#include <map>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int Nc,Nt;
    map<int,int> commonMap;
    int N,M,ele;
    cin >> N;
    vector<vector<int> > sets(N+1);
    for(int i = 1; i <= N; i++){
        scanf("%d",&M);
        commonMap.clear();
        for(int j = 0; j < M; j++){
            scanf("%d",&ele);
            if(commonMap.find(ele) == commonMap.end()){
                commonMap[ele] = 1;
                sets[i].push_back(ele);
            }
        }
        sort(sets[i].begin(),sets[i].end());
    }
    int K,a,b;
    cin >> K;
    for(int i = 0; i < K; i++){
        scanf("%d%d",&a,&b);
        vector<int> setA = sets[a];
        vector<int> setB = sets[b];
        Nc = Nt = 0;
        int curA = 0;
        int curB = 0;
        while(curA < setA.size() && curB < setB.size()){
            if(setA[curA] < setB[curB]){
                Nt++;
                curA++;
            }else if(setA[curA] > setB[curB]){
                Nt++;
                curB++;
            }else{
                Nc++;
                Nt++;
                curA++;
                curB++;
            }
        }
        if(curA < setA.size()) Nt += setA.size() - curA;
        if(curB < setB.size()) Nt += setB.size() - curB;
        printf("%0.1f%%
",(float)Nc / Nt * 100);
    }

    return 0;
}