C. Choose the Different Ones!

题解

我们只需要遍历1~k，这时会有四种情况：

1、只存于a数组中。

2、只存于b数组中。

3、同时存于ab数组中。

4、不存在于ab数组中。

对于情况三，这种数我们不需要去管，因为它可以算在任意的数组上。

那么我们只需要判断情况一和二的数是否都<=k/2，并且情况一二三的数总和为k.

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int main(){
    int t;
    cin>>t;
    while (t--){
        int n,m,k;
        bool bol=true;
        cin>>n>>m>>k;
        set<int> a,b;
        for (int i=1;i<=n;i++) {
            int x;
            cin>>x;
            a.insert(x);  //去重并且排序
        }
        for (int i=1;i<=m;i++){
            int x;
            cin>>x;
            b.insert(x);
        }
        int sum1=0,sum2=0;
        set<int>::iterator cnt1=a.begin(),cnt2=b.begin();
        for (int i=1;i<=k;i++){
            if (*cnt1==*cnt2 && *cnt1==i){  //情况三
                cnt1++;
                cnt2++;
            }
            else if (*cnt1==i){   //情况一
                cnt1++;
                sum1++;
            }
            else if (*cnt2==i){   //情况二
                cnt2++;
                sum2++;
            }
            else bol=false;   //不存在对应的数
        }
        if (sum1<=k/2 && sum2<=k/2 && bol) cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}