隐形的翅膀（离散化）

本文主要是介绍隐形的翅膀（离散化），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

背景

小杉终于进入了天堂。他看到每个人都带着一双隐形翅膀，他也想要。
（小杉是怎么看到的？……）
描述

天使告诉小杉，每只翅膀都有长度，两只翅膀的长度之比越接近黄金分割比例，就越完美。
现在天使给了小杉N只翅膀，小杉想挑出一对最完美的。
格式

输入格式

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

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

样例输入1

4
2 3 4 6
Copy
样例输出1

2
3
Copy
限制

每个测试点1s
提示

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

lolanv

//哇，人生第一道离散化耶
constgold:double=0.6180339887498949;//黄金比例，这个不能错
vark,min:double;x,y,n,i,j:longint;a:array[0..100001] of double;
procedure kui(x,y:longint);//递增快排
vari,j:longint;m,t:double;
begini:=x;j:=y;m:=a[(i+j)div 2];repeatwhile a[i]<m do inc(i);while a[j]>m do  dec(j);if i<=j then begint:=a[i];a[i]:=a[j];a[j]:=t;inc(i);dec(j);end;until i>j;if i<y then kui(i,y);if x<j then kui(x,j);
end;
beginread(n);for i:=1 to n do read(a[i]);kui(1,n);i:=1;j:=2;min:=999999.9;repeat//开始找吧！k:=a[i]/a[j]-gold;if abs(k)<min then beginmin:=abs(k);x:=i;y:=j;end;//这里很重要，有些同学可能会想到正负数上的if，这就需要两个判断了，但是这里可以用一个abs,因为就算<0是负数，也可以把绝对值看做一个比例值，不用考率正负，但是为了保证a[x]<a[y]所以说下一个if k>0是必要的；if k>0 then inc(j) else inc(i);until j>n;writeln((a[x]):0:0);writeln((a[y]):0:0);//其实可以用长整型的
end.

这篇关于隐形的翅膀（离散化）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---