1557 两个集合
题目来源： CodeForces
基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题
小X有n个互不相同的整数： p1,p2,...,pn 。他想把这些整数分到两个集合A和B里边。但是要符合下面两个条件。
· 如果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，如果不能实现，就为NO，否则为YES，分情况考虑:
如果 x 只能去 A 或 B ，那么两个数标记已使用，
如果 x 两个集合都可以去，那么如果去 A ，那么 b-x 这个数也只能去 A，如果去 B 那么 a-x 这个数只能去 B。
能满足任意标记即可，不能就输出NO
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 #define MX 100005 7 8 int n,a,b; 9 int dat[MX]; 10 bool use[MX]; 11 12 int bi_search(int x) 13 { 14 int l =1, r=n; 15 while (l<=r) 16 { 17 int mid = (l+r)>>1; 18 if (dat[mid]>x) r = mid - 1; 19 else if (dat[mid]<x) l = mid + 1; 20 else 21 { 22 if (use[mid]) return -1; 23 return mid; 24 } 25 } 26 return -1; 27 } 28 29 int main() 30 { 31 scanf("%d%d%d",&n,&a,&b); 32 for (int i=1;i<=n;i++) 33 scanf("%d",&dat[i]); 34 sort(dat+1,dat+1+n); 35 bool ok =1; 36 for (int i=1;i<=n;i++) 37 { 38 if (use[i]) continue; 39 int x = bi_search(a-dat[i]); 40 int y = bi_search(b-dat[i]); 41 if (x==-1&&y==-1) 42 { 43 ok=0; break; 44 } 45 else if (x!=-1&&y!=-1) 46 { 47 int xx = bi_search(a-dat[y]); 48 int yy = bi_search(b-dat[x]); 49 if (xx!=-1) 50 use[i] = use[x] = use[y] = use[xx] =1; 51 else if (yy!=-1) 52 use[i] = use[x] = use[y] = use[yy] =1; 53 else 54 { 55 ok=0; break; 56 } 57 } 58 else if (x!=-1) 59 use[i]=use[x]=1; 60 else if (y!=-1) 61 use[i]=use[y]=1; 62 } 63 if (ok) 64 printf("YES\n"); 65 else 66 printf("NO\n"); 67 return 0; 68 }