剑指offerITeye - 乐橙lc8

剑指offerITeye

2019年03月05日13时43分53秒 | 作者: 鸿福 | 标签: 输出,数组,两个 | 浏览: 1524

 

输入一个递加排序的数组和一个数字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 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

版权声明
本文来源于网络,版权归原作者所有,其内容与观点不代表乐橙lc8立场。转载文章仅为传播更有价值的信息,如采编人员采编有误或者版权原因,请与我们联系,我们核实后立即修改或删除。

猜您喜欢的文章