首页 > 代码库 > vijos 隐形的翅膀

vijos 隐形的翅膀

2024-10-16 19:06:39   202人阅读

背景

小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。

（小杉是怎么看到的？……）

描述

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

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

格式

输入格式

每组测试数据的
第一行有一个数N(2<=N<=30000)
第二行有N个不超过1e5的正整数，表示N只翅膀的长度。

20%的数据N<=100

输出格式

对每组测试数据输出两个整数，表示小杉挑选出来的一对翅膀。

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

样例1

样例输入1

42 3 4 6
Copy

样例输出1

23
Copy

限制

每个测试点1s

提示

你可以认为黄金分割比就是0.6180339887498949

来源

lolanv

 

这题比较神奇

技术分享
 1 /* 2     枚举一个数 a[i]  3     除以黄金比 得到 t=a[i]/gold 4     找到 与 t相差最小的数  5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<algorithm> 9 #define gold 0.618033988749894910 #define MAXN 3001011 12 using namespace std;13 14 int n,a[MAXN],Lx,Ry;15 16 double minn=1000000.0;17 18 inline void read(int&x) {19     x=0;int f=1;char c=getchar();20     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}21     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}22     x=x*f;23 }24 25 inline bool cmp(int a,int b) {26     return a<b;27 }28 29 inline double abs(double x) {30     if(x<0) return -x;31     return x;32 }33 34 int main() {35     read(n);36     for(int i=1;i<=n;i++) read(a[i]);37     sort(a+1,a+1+n,cmp);38     for(int i=1;i<=n;i++) {39         if(a[i]==0) continue;40         double p=a[i]/gold;41         int l=i,r=n,mid,k;42         while(l<=r) {43             mid=(l+r)>>1;44             if(a[mid]>p) r=mid-1,k=r;45             else l=mid+1;46         }47         if(a[k]==0) continue;48         double temp=abs((double)a[i]/a[k]-gold); 49         if(temp<minn) {50             minn=temp;51             Lx=a[i];52             Ry=a[k];53         }54     }55     printf("%d\n%d\n",Lx,Ry);56     return 0;57 }
90分代码

上面的方法不知道哪里有问题

只好换一种原理

技术分享
 1 /* 2     枚举两个数  3     计算黄金比 4     取最优值  5 */ 6 #include<cstdio> 7 #include<iostream> 8 #include<algorithm> 9 #define gold 0.618033988749894910 #define MAXN 3001011 12 using namespace std;13 14 int n,a[MAXN],Lx,Ry;15 16 double minn=1000000.0;17 18 inline void read(int&x) {19     x=0;int f=1;char c=getchar();20     while(c>‘9‘||c<‘0‘) {if(c==‘-‘) f=-1;c=getchar();}21     while(c>=‘0‘&&c<=‘9‘) {x=(x<<1)+(x<<3)+c-48;c=getchar();}22     x=x*f;23 }24 25 inline bool cmp(int a,int b) {26     return a<b;27 }28 29 inline double abs(double x) {30     if(x<0) return -x;31     return x;32 }33 34 inline bool judge(int x,int y) {35     double GOLD=(double)a[x]/(double)a[y];36     if(GOLD<gold) {37         if(gold-GOLD<minn) {38             minn=gold-GOLD;39             Lx=a[x];40             Ry=a[y];41         }42         return 1;43     }44     if(GOLD>gold) {45         if(GOLD-gold<minn) {46             minn=GOLD-gold;47             Lx=a[x];48             Ry=a[y];49         }50         return 0;51     }52 }53 54 int main() {55     read(n);56     for(int i=1;i<=n;i++) read(a[i]);57     sort(a+1,a+1+n,cmp);58     for(int i=1;i<=n;i++) {59         if(a[i]==0) continue;60         double p=a[i]/gold;61         int l=i,r=n,mid,k;62         while(l<=r) {63             mid=(l+r)>>1;64             if(judge(i,mid)) r=mid-1;65             else l=mid+1;66         }67     }68     printf("%d\n%d\n",Lx,Ry);69     return 0;70 }
AC代码

 

vijos 隐形的翅膀


联系
我们