PAT 甲级 刷题日记|A 1063 Set Similar

思路

这道题考察set的用法，直接使用set的find比用map标记的find更好，不会超时。

set的几个关键用法小结：

set的定义： set<typename> name;

set的特点：set内元素自动递增排序，且去重

set内元素的访问只能通过迭代器，而不能是下标：set<typename>:: iterator it ，遍历元素时，不能使用 < set.end() 而要写 != set.end()

set常用函数：

insert()时间复杂度是对数级别

find()时间复杂度 对数级别

erase()删除指定元素（value），删除指定位置元素（迭代器）， 删除区间元素（first, last)

代码

#include <bits/stdc++.h>
using namespace std;

const int maxn = 55;
set<int> s[maxn];

int main() {
    int n;
    cin>>n;
    for (int i = 1; i <= n; i++) {
        int len;
        cin>>len;
        for (int j = 0; j < len; j++) {
            int number;
            cin>>number;
            s[i].insert(number);
        }
    }
    int q;
    cin>>q;
    while (q--) {
        int q1, q2;
        cin>>q1>>q2;
        double nc = 0, ns = s[q1].size();
        for (auto it = s[q2].begin(); it != s[q2].end(); it++) {
            if (s[q1].find(*it) == s[q1].end()) ns++;
            else nc++;
        }
        double sim = nc / ns * 100;
        printf("%.1f%\n", sim);
    }
}