Anfangen的live house

Anfangen的live house

题解 P2141 【珠心算测验】

posted on 2017-10-31 22:23:48 | under 题解 |

STL set题解

STL大法好

一想到去重,那么我们就可以把元素丢到一个集合里。

从此不用担心重复问题。

基本思路:

创建一个查找集合,一个去重答案集合

(由于集合的插入和查找的时间复杂度皆为O(log n),加上这题n的数据范围只有100,所以可以使用集合)

枚举。

时间复杂度? $$O(n^2logn)$$ 吧

#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;
}