题解：UVA11849 CD

Bobi2014 · 2025-10-03 16:52:42 · 题解

这是一道可癌的看不懂的题。

前置知识

• 谷歌翻译
• set

思路

题目的意思看前置知识。

因为题目要求只有两个人都有的光盘数量，所以我们可以用总光盘数 - 光盘的并集。

那么就可以用把所有光盘放入 set，set 的大小就是并集的大小，最后输出 n + m - size。

一组测试数据的时间复杂度为 O((n + m) \times \log(n + m))。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
set<int> s;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while(true){
        cin >> n >> m;
        if(n == 0 and m == 0){
            break;
        }
        s.clear();
        for(int i = 1;i <= n;i ++){
            int x;
            cin >> x;
            s.insert(x);
        }
        for(int i = 1;i <= m;i ++){
            int x;
            cin >> x;
            s.insert(x);
        }
        cout << n + m - s.size() << '\n';
    }
    return 0;
}