1063. Set Similarity (25)

时间限制：300ms
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%

=====================================
这题目看起来挺简单，但是因为
1.数据量大
2.数值范围大
所以
1.要考虑求交集并集的最佳算法
2.不能用bitmap来用空间换时间
这个求交集并集（数量）的算法其实说来也不难，
有两个集合A,B，先假设
他们并集的大小uSize = |A|+|B|
交集的大小iSize = 0
集合进行排序(最小时间复杂度O(nlogn))后，可以用O(1)的算法找出并集交集：

A元素指针 ptrA = A.begin()
B元素指针 ptrB = B.begin()
while 列表A/B都没有遍历尽:
valA = *ptrA
valB = *ptrB
if valA == valB:
ptrA++
ptrB++
iSize ++
uSize -- #去掉多余的元素
elif valA > valB:
#数值小的往后挪动一格
ptrB++
else:
ptrA++

具体代码如下，后来想想其实用实现更方便一点:)

#include
#include
#include
using namespace std;
double getSimi(vector a, vector b)
{
vector *ptrA = &a;
vector *ptrB = &b;
if( a.size() > b.size())
{
//保证ptrA集合数目小
ptrB = &a;
ptrA = &b;
}
sort(ptrA->begin(), ptrA->end());
sort(ptrB->begin(), ptrB->end());
int iSize = 0;
int uSize = ptrB->size() + ptrA->size();
vector::iterator itA = ptrA->begin();
vector::iterator itB = ptrB->begin();
while(itA != ptrA->end() && itB!=ptrB->end())
{
long valA = *itA;
long valB = *itB;
if(valA == valB)
{
iSize ++;
uSize --;
itA++;
itB++;
}
else if(valA > valB)
{
//B队列下移一位
itB++;
}
else
{
//A队列下移一位
itA++;
}
}
return static_cast(iSize)/uSize;
}
int main()
{
int N;
scanf("%d", &N);
vector *arySets = new vector[N];
for(int i=0; i

测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	0	720	12/12
1	答案正确	0	720	3/3
2	答案正确	0	790	3/3
3	答案正确	10	790	3/3
4	答案正确	260	990	4/4