题目描述
给你a,b和n个数p[i]，问你如何分配这n个数给A,B集合，并且满足：
若x在集合A中，则a-x必须也在集合A中。
若x在集合B中，则b-x必须也在集合B中。
输入描述:
第一行 三个数 n a b 1<=n<=1e5 1<=a,b<=1e9 第二行 n个数 p1 p2 p3...pn 1<=pi<=1e9
输出描述:
如果可以恰好分开就输出第一行 YES 然后第二行输出 n个数 分别代表pi 是哪个集合的 0 代表是A集合 1代表是B 集合 不行就输出NO 放在哪个集合都可以的时候优先放B
输入
4 5 9 2 3 4 5
输出
YES 0 0 1 1
输入
3 3 4 1 2 4
输出
NO
解题思路：并查集
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
map<int,int>mp;
int a[100010];
int f[100010];
int getf(int v)
{if(f[v]==v)return v;else{f[v]=getf(f[v]);return f[v];}
}
void merge(int x,int y)
{int t1=getf(x);int t2=getf(y);if(t1!=t2)f[t2]=t1;
}
int main()
{int n,A,B;scanf("%d%d%d",&n,&A,&B);int ma=0;for(int i=1; i<=n; i++){scanf("%d",&a[i]);mp[a[i]]=i;ma=max(ma,a[i]);}if(ma>max(A,B))printf("No\n");else{for(int i=0; i<=n+1; i++)f[i]=i;for(int i=1; i<=n; i++){if(mp[B-a[i]])//B-a[i]存在merge(i,mp[B-a[i]]);//合并序号i和mp[B-a[i]]的序号elsemerge(i,0);//如果B-a[i]不存在,放到和0一个集合中，即放到A集合里面if(mp[A-a[i]])merge(i,mp[A-a[i]]);//A-a[i]存在合并序号i和mp[A-a[i]]的序号elsemerge(i,n+1);//如果A-a[i]不存在，放到和n+1一个集合中，即放到B集合中}
// for(int i=0;i<=n;i++)
// printf("%d>>>>\n",f[i]);
//1>>>>
//1>>>>
//3>>>>
//3>>>>int fa=getf(0);int fb=getf(n+1);if(fa==fb)//如果一个数存在两个集合中,则与题意矛盾{printf("NO\n");}else{printf("YES\n");for(int i=1; i<=n; i++){if(i!=1)printf(" ");int ff=getf(i);if(ff==fa)printf("0");else//*****不可以用else if(ff==fb),虽然把mp[B-a[i]]存在的情况和i进行了合并//但是并不代表一定与n+1进行了合并。。。printf("1");}printf("\n");}}return 0;
}