51Nod 1557 两个集合（二分）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1557

题意：

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

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

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

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

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

思路：

先排序然后一个一个分析过去，用二分法查找对应的数。

一开始的时候考虑的不够仔细，就是说如果a-x和b-x都存在的话，就必须得进一步的分析，因为x只能和其中一个数在一个集合中。所以在这种情况下还需要判断一下b-（a-x）和a-（b-x）的情况，只要其中一个能找到那就可以。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<queue>
 7 using namespace std;
 8 
 9 const int maxn=1e5+5;
10 
11 int n,a,b;
12 int c[maxn];
13 
14 bool solve(int num)
15 {
16     int L=1,R=n;
17     while(L<=R)
18     {
19         int mid=(L+R)/2;
20         if(c[mid]>num)  R=mid-1;
21         else if(c[mid]<num)  L=mid+1;
22         else return true;
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     //freopen("D:\input.txt","r",stdin);
30     while(~scanf("%d%d%d",&n,&a,&b))
31     {
32         for(int i=1;i<=n;i++)
33             scanf("%d",&c[i]);
34         sort(c+1,c+n+1);
35         for(int i=1;i<=n;i++)
36         {
37             bool A=solve(a-c[i]);
38             bool B=solve(b-c[i]);
39             if(!A && !B)
40             {
41                 printf("NO
");
42                 return 0;
43             }
44             if(A && B)
45             {
46                 bool C=solve(b-(a-c[i]));
47                 bool D=solve(a-(b-c[i]));
48                 if(!C && !D)
49                 {
50                     printf("NO
");
51                     return 0;
52                 }
53             }
54         }
55         printf("YES
");
56     }
57 }