51Nod 1557 两个集合（二分）-白红宇

51Nod 1557 两个集合（二分）

阅读量：5162 次

发布时间：2019-06-13

本文共 744 字，大约阅读时间需要 2 分钟。

题意：

小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
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            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]

转载于:https://www.cnblogs.com/zyb993963526/p/6701572.html

你可能感兴趣的文章