Codevs 2765 隐形的翅膀

2765 隐形的翅膀

 

题目描述 Description

天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例（黄金分割比= 0.6180339887498949），就越完美。

现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。

输入描述 Input Description

第一行有一个数N(2≤N≤30000)。

第二行有N个不超过106的正整数，表示N只翅膀的长度。

输出描述 Output Description

输出两个整数，分两行，表示小杉挑选出来的一对翅膀的长度。

注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。

样例输入 Sample Input

4

2 3 4 6

样例输出 Sample Output

2

3

数据范围及提示 Data Size & Hint

2≤N≤30000

二分查找

#include<bits/stdc++.h>

#define maxn 200000

const double gold=0.6180339887498949;

using namespace std;

double a[maxn];

double ans[maxn];

int c[maxn];

int n;

void solve(int k){

    int l=,r=k-;

    int mid=(l+r)>>;

    while(l<r){

        if(a[mid]/a[k]>gold) r=mid;

        else l=mid+;

        mid=(l+r)>>;

    }

    if(abs(a[l+]/a[k]-gold)<abs(a[l]/a[k]-gold) )l++;

    if(abs(a[l-]/a[k]-gold)<abs(a[l]/a[k]-gold)) l--;//二分

    ans[k]=abs(a[l]/a[k]-gold);

    c[k]=l;

}

int main(){

    cin>>n;

    for(int i=;i<=n;i++)

        cin>>a[i];

    sort(a+,a+n+);

    for(int i=;i<=n;i++)

        solve(i);

    double Min=;int point=;

    for(int i=;i<=n;i++){

          if(Min-ans[i]>=0.0000000001){

            Min=ans[i];

            point=i;

          }

    }

    cout<<a[c[point]]<<endl;

    cout<<a[point]<<endl;

    return ;

}