二分查找 HDOJ 2141 Can you find it?
2024-09-12 02:00:58
/*
题意:给出一个数,问是否有ai + bj + ck == x
二分查找:首先计算sum[l] = a[i] + b[j],对于q,枚举ck,查找是否有sum + ck == x
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std; typedef long long ll;
const int MAXN = 5e2 + ;
const int INF = 0x3f3f3f3f;
ll a[MAXN], b[MAXN], c[MAXN];
ll sum[MAXN*MAXN];
int tot; bool my_binary_search(int l, int r, ll k) {
while (l < r) {
int mid = (l + r) >> ;
if (sum[mid] == k) return true;
else if (sum[mid] > k) r = mid;
else l = mid + ;
}
return false;
} int main(void) { //HDOJ 2141 Can you find it?
//freopen ("HDOJ_2141.in", "r", stdin); int l, n, m, s, cas = ;
while (scanf ("%d%d%d", &l, &n, &m) == ) {
for (int i=; i<=l; ++i) scanf ("%I64d", &a[i]);
for (int i=; i<=n; ++i) scanf ("%I64d", &b[i]);
for (int i=; i<=m; ++i) scanf ("%I64d", &c[i]);
scanf ("%d", &s); printf ("Case %d:\n", ++cas);
sort (a+, a++l); sort (b+, b++n); sort (c+, c++m);
tot = ;
for (int i=; i<=l; ++i) {
for (int j=; j<=n; ++j) {
sum[++tot] = a[i] + b[j];
}
}
sort (sum+, sum++tot); ll mn = a[] + b[] + c[], mx = a[l] + b[n] + c[m];
while (s--) {
ll q; scanf ("%I64d", &q);
if (q < mn || q > mx) {
puts ("NO"); continue;
}
bool flag = false;
for (int i=; i<=m; ++i) {
int p = lower_bound (sum+, sum++tot, q - c[i]) - sum;
if (p < || p > tot) continue;
if (sum[p] + c[i] == q) {
flag = true; puts ("YES"); break;
}
//if (my_binary_search (1, tot, q - c[i])) {
//flag = true; puts ("YES"); break;
//}
}
if (!flag) {
puts ("NO");
}
}
} return ;
}
最新文章
- 【shell 大系】Linux Shell常用技巧
- Unity3D入门
- [Maven]Maven详解
- 深入理解openstack网络架构(2)----Basic Use Cases
- 自学php笔记
- (菜鸟要飞系列)四,基于Asp.Net MVC5的后台管理系统(zTree绑定Json数据生成树)
- 二分查找or折半查找
- Spring AOP应用实例demo
- 有一种acm题目叫做,奇葩!
- JAVA POI 应用系列(2)--读取Excel
- 【highchart】经典问题
- Java基础机试题
- LeetCode(52)-Remove Linked List Elements
- BeanUtils 日期转换(本地格式yyyy-MM-dd)转换成date
- webpack安装
- 深度学习之GRU网络
- DEA和模糊综合评价
- GanttProject 项目管理软件的优点
- mongodb相关文章
- ELK收集Nginx|Tomcat日志