51Nod-1557-两个集合

2019-11-06 06:22:37

字体：大中小

来源：转载

供稿：网友

ACM模版

描述

题解

我用的方法复杂度是 O（nlogn），快排+二分，思路挺简单，但是容易漏，要想全才行。这个问题也就是数对儿问题，x+pA=a 或者 x+pB=b。

首先，我们只用分析 NO 的情况，其他的都是 YES，NO 的情况有两种： One：x 既不在 A 中，也不在 B 中，即找不到 a-x 和 b-x，NO； Two：x 既可以在 A 中，也可以在 B 中，也就是找到了 a-x 和 b-x，如果 x 在 A 中，那么 b-x 一定不在 B 中，因为数唯一，所以 b-x 只能在 A 中，也就是说必须存在 a-(b-x)，如果不存在就行不通，同理得如果 x 在 B 中，则必须存在 b-(a-x)，如果不存在就行不通，那么如果两个方案都行不通了，也就是说 NO 了。其次，……，对了，没有其次。:-D

貌似我的题解挺长的，其实我并不想写这么长的。

代码

#include <iostream>#include <algorithm>#define YES 1#define NO 0using 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"; return 0;}

上一篇：test

下一篇：struts-2.3.31和struts-2.5.10引入jar以及配置web.xml和struts.xml

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注