Can you find it? HDU-2141 (二分查找模版题)
Description
Give you three sequences of numbers A, B, C, then we give you a number X. Now you need to calculate if you can find the three numbers Ai, Bj, Ck, which satisfy the formula Ai+Bj+Ck = X.
Input
There are many cases. Every data case is described as followed: In the first line there are three integers L, N, M, in the second line there are L integers represent the sequence A, in the third line there are N integers represent the sequences B, in the forth line there are M integers represent the sequence C. In the fifth line there is an integer S represents there are S integers X to be calculated. 1<=L, N, M<=500, 1<=S<=1000. all the integers are 32-integers.
Output
For each case, firstly you have to print the case number as the form "Case d:", then for the S queries, you calculate if the formula can be satisfied or not. If satisfied, you print "YES", otherwise print "NO".
Sample Input
3 3 3
1 2 3
1 2 3
1 2 3
3
1
4
10
Sample Output
Case 1:
NO
YES
NO
思路:枚举三个数组,时间复杂度O(N^3),肯定会超时。所以可以把前两个数组的和先枚举出来,存在数组sum[260000]中,
由于要找是否存在sum[i] + c[j] = X, 可以把问题转换为在sum数组中查找是否有X-c[j]这个数。用二分查找sum数组即可。时间复杂度为: S * c数组的大小 * log(sum数组的大小)
注意:不能在c数组中二分查找是否有X-sum[i]这个数,因为其时间复杂度为: S * sum数组的大小 * log(c数组的大小),由于题目中sum数组大小最大为250000,c数组大小最大为500,S为1000,所以会超时
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm> using namespace std; int a[], b[], c[];
int sum[];
int L, N, M, S, X;
int cnt = ; int main()
{
while(scanf("%d %d %d", &L, &N, &M) != EOF)
{
for(int i = ; i < L; ++i)
scanf("%d", &a[i]);
for(int i = ; i < N; ++i)
scanf("%d", &b[i]);
for(int i = ; i < M; ++i)
scanf("%d", &c[i]); int k = ;
for(int i = ; i < L; ++i)
for(int j = ; j < N; ++j)
sum[k++] = a[i] + b[j]; sort(sum, sum+k);
scanf("%d", &S);
printf("Case %d:\n", cnt++);
while(S--)
{
scanf("%d", &X); int flag = ;
for(int i = ; i < M; ++i)
{
int target = X - c[i];
int left = , right = k; while(left <= right)
{
int mid = (left + right) / ;
if(sum[mid] == target)
{
flag = ;
break;
}
else if(sum[mid] < target)
left = mid + ;
else
right = mid - ;
}
if(flag == )
{
printf("YES\n");
break;
}
}
if(flag == )
printf("NO\n"); }
} return ;
}
最新文章
- 如何修改Xampp中MySQL的root密码?
- Swift3.0语言教程使用Unicode范式标准化获取字符串
- win7系统中ftp服务器搭建方法(多图)
- Python pass 语句使用示例
- Fzu Problem 2082 过路费 LCT,动态树
- IntelliJ IDEA 中module的dependencies是其它module时的注意事项
- python高级编程之选择好名称:pepe8和命名最佳实践
- Java学习之自定义异常
- Swift 简简单单实现手机九宫格手势密码解锁
- 【转】Django HTTP请求的处理流程
- npm安装
- P神的SDFZ考试题 C题
- 小隐隐于野:基于TCP反射DDoS攻击分析
- spring cloud微服务下手动回滚事务
- SAP MM ME81N PO Value Analysis报表中Net Value 为负数是怎么回事?
- 转://RMAN跨平台可传输表空间和数据库
- Python3基础 list + *运算 扩充列表
- centos7 php性能调优
- Mysql的myqldump命令使用方法(备份与还原)
- python Genarator函数
热门文章
- vue报错 error: data.push is not a function
- elasticsearch 中文API 基于查询的删除(九)
- Leetcode95. Unique Binary Search Trees II不同的二叉搜索树2
- html2canvas JS截图插件
- 事务一致性理解 事务ACID特性的完全解答
- XSS“从1到0”
- Scrapy框架Crawler模板爬虫
- Java程序员面试题收集(3)
- Web调取摄像头拍照
- Python eval()函数的用法