首页 > 代码库 > 二分查找（隐形的翅膀vijos1237）
二分查找（隐形的翅膀vijos1237）
背景
小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。
（小杉是怎么看到的？……）
描述
天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。
现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。
格式
输入格式
每组测试数据的
第一行有一个数N(2<=N<=30000)
第二行有N个不超过1e5的正整数，表示N只翅膀的长度。
20%的数据N<=100
输出格式
对每组测试数据输出两个整数，表示小杉挑选出来的一对翅膀。
注意，比较短的在前，如果有多对翅膀的完美程度一样，请输出最小的一对。
样例1
样例输入1
Copy
样例输出1
Copy
限制
每个测试点1s
你可以认为黄金分割比就是0.6180339887498949
就是二分的思想啦，具体实现可以看代码~
#include<bits/stdc++.h>#define maxn 200000const 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;}
二分查找（隐形的翅膀vijos1237）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。