题目描述:
输入一个递增排序的数组和一个数字S,在数组中查找两个数,是的他们的和正好是S,如果有多对数字的和等于S,输出两个数的乘积最小的。
输入:
每个测试案例包括两行:
第一行包含一个整数n和k,n表示数组中的元素个数,k表示两数之和。其中1 <= n <= 10^6,k为int
第二行包含n个整数,每个数组均为int类型。
输出:
对应每个测试案例,输出两个数,小的先输出。如果找不到,则输出“-1 -1”
样例输入:
6 15
1 2 4 7 11 15
样例输出:
4 11
刚开始还以为是不是要二分之类的。其实没有那么复杂。
因为是递增数组,所以第一次求出a[low]+a[high]==k,则是乘机最小的那个。因为根据柯西定理还是啥的,当两个数x+y=k,当x和y越接近乘机越大。证明如下:
x+y=k
两边平方:
(x+y)^2=k^2
然后继续变:
(x-y)^2+4xy=k^2
很显然x和y越接近,xy就越大。故让x和y尽量相差很大。
#include <stdio.h> int main(){ int n,k,low,high; int a[1000000]; while( scanf("%d%d",&n,&k) != EOF ){ for( int i=0; i<n; i++){ scanf("%d",&a[i]); } low = 0; high = n-1; while( low < high ){ if( (a[low]+a[high]) == k ) break; else if( (a[low]+a[high]) > k ) high--; else low++; } if( low< high ) printf("%d %d\n",a[low],a[high]); else printf("-1 -1\n"); } return 0; } /************************************************************** Problem: 1352 User: 从此醉 Language: C++ Result: Accepted Time:1430 ms Memory:4856 kb ****************************************************************/
参考:http://www.acmerblog.com/intervier-offer17-jiudu-1352-4547.html
相关推荐
使用vs2010编写,直接用vs2010打开加压后的.sln文件即可看到...九度OJ上面的剑指Offer习题全套答案,全部AC,且具有较好的时间复杂度。部分参考网络上的idea,但代码已经尽量要求简洁,是OJ练习不可多得的参考代码。
九度oj 题目1369:字符串的排列 剑指offer里面的题目 自己写的代码,供参考!
这是九度OJ-题目1509:树中两个结点的最低公共祖先的测试数据,input.txt是输入数据,output.txt是输出数据。
本文件为剑指offer一书的大部分的代码,WA表示没有通过九度在线测试平台的所有测试用例,PASS代表本题先跳过。 ----- 毕业设计,课程设计,项目源码均经过助教老师测试,运行无误,欢迎下载交流 ----- 下载后请首先...
interview 剑指offer、九度OJ等面试笔试题的代码实现 语言:C/C++/python
建议在闲暇时挂机,或有多余的电脑挂机,也可以在自己的电脑上,安装虚拟机,在虚拟机上运行挂机软件,工作和挂机两不误 九度淘宝直通车点击软件出色功能 1.由全国各地众多挂机者自动点击,流量来源分布广泛而...
九度智能seo优化软件是一款针对搜索引擎的点击类软件。软件适用于百度、谷歌、360搜索、搜狗、搜搜、淘宝、天猫等等搜索引擎,可以用来提高...绝对是专业人士必备的seo优化软件,您值得拥有! 九度智能seo优化软件截图
建议在闲暇时挂机,或有多余的电脑挂机,也可以在自己的电脑上,安装虚拟机,在虚拟机上运行挂机软件,工作和挂机两不误。 九度搜索引擎点击优化软件出色功能 1.由全国各地众多挂机者自动点击,流量来源分布广泛而...
完整可以用在二次开发,节约时间成本,
九度OJ八皇后问题,主要是主对角线和副对角线的判断上面优化。在九度1140上面已经AC
九度 ACM 很好的九度 ACM解题报告 不错 大家可以下下来看看 九度内推
ZJU考研机试真题 九度1006ZOJ问题
资源分享者,资源爱好者,我是浪杉,点我资料关注,每日不定时分享全网优质源码!
JobduOJ-InterviewQuestions九度OJ-剑指Offer解题代码这是九度OJ剑指Offer系列的解题代码,一共有51道题。
建议在闲暇时挂机,或有多余的电脑挂机,也可以在自己的电脑上,安装虚拟机,在虚拟机上运行挂机软件,工作和挂机两不误出色功能1.由全国各地众多挂机者自动点击,流量来源分布广泛而合理;2.点击逼真,点击过程完全...
九度智能SEO优化软件是九度搜索引擎点击优化软件重新开发版,本是针对搜索引擎的SEO优化类软件,2016年10月正式上线。软件可像真人点击一样,自动点击百度、谷歌、360搜索、搜狗、搜搜、淘宝、天猫等搜索引擎内的...
九度求职经验系列之“实习生”篇.pdf 讲述了九度求职经验相关内容
九度算法实现EXCEL排序 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例,首先输出1行“Case i:”,其中 i 是测试用例的编号(从1开始)。随后在 N 行中输出按要求排序后的结果...
ZJU考研机试真题 九度1004Median
计算机机试指南九度OJ机试题目解析复试机试参考,适用于计算机考研的同学,文档整理汇总了各个分类,方便入门和刷题参考。