题解 P2141 【珠心算测验】
Anfangen
2017-10-31 22:23:48
#STL set题解
###STL大法好
一想到去重，那么我们就可以把元素丢到一个集合里。
从此不用担心重复问题。
基本思路：
创建一个查找集合，一个去重答案集合
（由于集合的插入和查找的时间复杂度皆为O(log n)，加上这题n的数据范围只有100，所以可以使用集合）
枚举。
时间复杂度？ $$O(n^2logn)$$ 吧
```cpp
#include <cstdio>
#include <iostream>
#include <set>
using namespace std;
set<int> num; // 查找用集合
set<int> res; // 去重用集合
int n,a[105],tmp;
int main(){
//freopen("count.in","r",stdin);
//freopen("count.out","w",stdout);
cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]; //输入数值
num.insert(a[i]); //用集合方便查找
}
for(int i=1;i<=n;++i){ //枚举a[i]
for(int j=i+1;j<=n;++j){ //枚举a[j]
int tmp=a[i]+a[j]; //接下来定义tmp，它是所枚举的两数之和
set<int>::iterator it=num.find(tmp); // 直接在集合中查找tmp
//注意，find函数返回的是一个迭代器，所以要用一个迭代器来存储find的返回值
if(it!=num.end()) { // 在find中，如果没有找到集合中的元素，那么迭代器会在集合的末尾。
//所以如果it不在集合末尾，那么说明it在集合中出现过
res.insert(*it); //在去重集合中插入
}
}
}
cout<<res.size();//直接输出集合内元素数量
return 0;
}
```