zcmimi's blog
avatar
zc
2019-12-21 19:47:00
  • 本文总阅读量
查看原题

点击跳转

首先,我们只用分析 NO 的情况,其他的都是 YES,NO 的情况有两种:

  1. x 既不在 A 中,也不在 B 中,即找不到 a-x 和 b-x,NO;
  2. x 既可以在 A 中,也可以在 B 中,也就是找到了 a-x 和 b-x,如果 x 在 A 中,那么 b-x 一定不在 B 中,因为数唯一,所以 b-x 只能在 A 中,也就是说必须存在 a-(b-x),如果不存在就行不通,同理得如果 x 在 B 中,则必须存在 b-(a-x),如果不存在就行不通,那么如果两个方案都行不通了,也就是说 NO 了。
#include <iostream>
#include <algorithm>

#define YES 1
#define NO 0

using namespace std;

const int MAXN = 1e5 + 10;

int p[MAXN];

int bs(int l, int h, int v)
{
    int m;
    while (l < h)
    {
        m = (l + h) >> 1;
        if (p[m] == v)
        {
            return YES;
        }
        if (p[m] < v)
        {
            l = m + 1;
        }
        else
        {
            h = m;
        }
    }
    return NO;
}

int main(int argc, const char * argv[])
{
//    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);

    int n, a, b;
    cin >> n >> a >> b;

    for (int i = 0; i < n; i++)
    {
        scanf("%d", p + i);
    }
    sort(p, p + n);

    for (int i = 0; i < n; i++)
    {
        bool A = bs(0, n, a - p[i]);
        bool B = bs(0, n, b - p[i]);
        if (!A && !B)
        {
            cout << "NO\n";
            return 0;
        }
        if (A && B)
        {
            bool A_ = bs(0, n, a - b + p[i]);
            bool B_ = bs(0, n, b - a + p[i]);
            if (!A_ && !B_)
            {
                cout << "NO\n";
                return 0;
            }
        }
    }
    cout << "YES\n";
}
51nod 1557 两个集合
comment评论
Search
search