最新消息:点击查看大S的省钱秘笈

Vijos P1237 隐形的翅膀 C语言版

Vijos题解 Slyar 93浏览 0评论

文章作者:姜南(Slyar) 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。

描述 Description

小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀,他也想要。
天使告诉小杉,每只翅膀都有长度,两只翅膀的长度之比越接近黄金分割比例,就越完美。
现在天使给了小杉N只翅膀,小杉想挑出一对最完美的。

输入格式 Input Format

每组测试数据的
第一行有一个数N(2<=N<=30000)
第二行有N个不超过1e5的正整数,表示N只翅膀的长度。
20%的数据N<=100
你可以认为黄金分割比就是0.6180339887498949

输出格式 Output Format

对每组测试数据输出两个整数,分两行,表示小杉挑选出来的一对翅膀。
注意,比较短的在前,如果有多对翅膀的完美程度一样,请输出最小的一对。

Tip:快排+贪心。精度、精度、精度!一定要注意精度问题,还有就是整型相除的结果是整型,要变成实型才可以。。。因为精度又WA了N次。。。

#include <stdio.h>

#define gold 0.6180339887498949

void qsort(long s[],int l,int r){
int i,j,x;
if(l<r){
i=l;
j=r;
x=s[i];
while(i<j){
while(i<j&&s[j]>x) j--;
if(i<j) s[i++]=s[j];
while(i<j&&s[i]<x) i++;
if(i<j) s[j--]=s[i];
}
s[i]=x;
qsort(s,l,i-1);
qsort(s,i+1,r);
}
}

int main(){
long n,a[30001],i,p=1,q=2,x,y;
double min=100;
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
qsort(a,1,n);
while(q<=n){
if (fabs(a[p]*1.0/a[q]-gold)<min){
x=a[p];
y=a[q];
min=fabs(a[p]*1.0/a[q]-gold);
}
if (a[p]*1.0/a[q]<gold) p++;
else q++;
}
printf("%d\n%d\n",x,y);
system("pause");
return 0;
}

转载请注明:Slyar Home » Vijos P1237 隐形的翅膀 C语言版

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址