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=1,r=k-1; int mid=(l+r)>>1; while(l<r){ if(a[mid]/a[k]>gold) r=mid; else l=mid+1; mid=(l+r)>>1; } if(abs(a[l+1]/a[k]-gold)<abs(a[l]/a[k]-gold) )l++; if(abs(a[l-1]/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=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(int i=2;i<=n;i++) solve(i); double Min=1;int point=0; for(int i=2;i<=n;i++){ if(Min-ans[i]>=0.0000000001){ Min=ans[i]; point=i; } } cout<<a[c[point]]<<endl; cout<<a[point]<<endl; return 0; }