51nod 1557 两个集合 (严谨的逻辑题)

题目：

1557 两个集合

题目来源： CodeForces

基准时间限制：1 秒空间限制：131072 KB 分值: 40 难度：4级算法题

小X有n个互不相同的整数：

· 如果x属于A，那么a-x也肯定属于A。

· 如果x属于B，那么b-x也肯定属于B。

判断一下是否存在一种方案来分配这些数字到集合A，B中。

注意：如果一个集合为空也是可以的。

Input

单组测试数据。
第一行有三个整数n,a,b (1≤n≤10^5; 1≤a,b≤10^9)。
第二行有n个不一样的整数 p1,p2,...,pn (1≤pi≤10^9).

Output

如果可行，那么输出YES，否则输出NO。

Input示例

样例输入1
4 5 9
2 3 4 5

Output示例

样例输出1
YES





















题意很清楚就是把所有的数字按要求分在A,B集合中，看是否能全部分完。


看似很简单，但是有很多坑点，需要把所有的逻辑都想清楚再下笔。

解法：
　　　　首先我们看到这道题肯定会想到二分图的解法。
　　　　二分图是相邻的点要染成不同色，看是否能把整个图只用两种颜色染色。
　　　　这道题是相邻的点（a[i]+a[j]==A || a[i]+a[j]==B）要染成同色，看是否能用两种颜色表示。（注意的是两种颜色可能相同(A == B)）
　　　　但是和二分图很不同的是，当一个点可以在A中而且可以在B中时，用二分图的逻辑有点行不通了。

　　所以我们换个思路：
　　　　
　　　　当某个点只能存在A中/只能存在于B中时，我们就把这个点和与之匹配的点（A-a[i]/B-a[i]）放在A/B中。
　　　　一趟一趟的扫所有的点，如果某一次没有能放在A/B中的点了，
　　　　　　1.n个点中还有点没有被放在A/B中，那就不能分完，输出NO。
　　　　　　2.n个点全部放在A/B中了，那就能分完，输出YES。

　　　　注意的就是如果A == B,可能会陷入死循环，需要特殊处理A == B，直接看是否能将全部点放在A/B中就可以。


代码：

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <set>
#include <math.h>
#include <queue> 
using namespace std;
typedef long long ll;
#define INF 2147483647

int s[100010];


map<int, bool> in; // 表示数字没有被使用过，所有的数字都在大集合里 

int main(){
    int n,a,b;
    cin >> n >> a >> b;
    for(int i = 0;i < n; i++){
        cin >> s[i];
        in[s[i]] = true;
    }
    
    int count = 0;    //记录多少个数字被使用过 
    
    while(true){
        //标记当前循环是否有数字匹配 
        bool update = false;
        
        for(int i = 0;i < n; i++){ 
            if(!in[s[i]]) continue;    //这个数字被使用过了，不再计算 
            if(in[a-s[i]] && !in[b-s[i]]){
                //在A集合中能找到匹配对象，B集合中找不到，一定要放在A集合中 
                in[a-s[i]] = false;    
                in[s[i]] = false;
                count += 2;
                update = true;
            }else if(!in[a-s[i]] && in[b-s[i]]){
                //在B集合中能找到匹配对象，A集合中找不到，一定要放在B集合中
                in[b-s[i]] = false;
                in[s[i]] = false;
                count += 2;
                update = true;
            }else if(in[a-s[i]] && in[b-s[i]] && a == b){
                //如果a == b，全部放在一个集合中就可以了 
                in[a-s[i]] = false;    
                in[s[i]] = false;
                count += 2;
                update = true;
            }
        }
        //如果放了n个数字了，说明可以分配 
        if(count >= n) break;
        //如果放不够n个数字，而且再也找不到匹配了，说明无法分配 
        if(!update){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}