51Nod 1557 两个集合（二分）

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

题意：

小X有n个互不相同的整数： p1,p2,...,pn 。他想把这些整数分到两个集合A和B里边。但是要符合下面两个条件。

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

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

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

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

思路：

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

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

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 using namespace std;

 const int maxn=1e5+;

 int n,a,b;

 int c[maxn];

 bool solve(int num)

 {

     int L=,R=n;

     while(L<=R)

     {

         int mid=(L+R)/;

         if(c[mid]>num)  R=mid-;

         else if(c[mid]<num)  L=mid+;

         else return true;

     }

     return false;

 }

 int main()

 {

     //freopen("D:\\input.txt","r",stdin);

     while(~scanf("%d%d%d",&n,&a,&b))

     {

         for(int i=;i<=n;i++)

             scanf("%d",&c[i]);

         sort(c+,c+n+);

         for(int i=;i<=n;i++)

         {

             bool A=solve(a-c[i]);

             bool B=solve(b-c[i]);

             if(!A && !B)

             {

                 printf("NO\n");

                 return ;

             }

             if(A && B)

             {

                 bool C=solve(b-(a-c[i]));

                 bool D=solve(a-(b-c[i]));

                 if(!C && !D)

                 {

                     printf("NO\n");

                     return ;

                 }

             }

         }

         printf("YES\n");

     }

 }

巴特西

51Nod 1557 两个集合（二分）

最新文章

热门文章