正題

題目鏈接：https://vijos.org/p/1237

---

大意

有n支長度不一翅膀，要求選擇兩只最接近黃金分割率的翅膀。

---

解題思路

暴力枚舉O(n2)O(n2)是過不了的。

所有這就要用到離散了，給翅膀長度排序。
然后一個i和一個j，根據(jù)算出的比黃金分割率大或小可以判斷選擇i和j那個需要增加翅膀。
時間復雜度O(nlogn)O(nlogn)

---

代碼

#include<cstdio> #include<algorithm> using namespace std; const double bl=0.6180339887498949;//黃金分割率 int n,s1,s2; double a[30001],k,mins; double abs(double k)//abs {if (k<0) return -k;return k; } int main() {scanf("%d",&n);for (int i=1;i<=n;i++)scanf("%lf",&a[i]);sort(a+1,a+1+n);int i=1;int j=2;mins=2147483647;while (j<=n){k=a[i]/a[j]-bl;//距離黃金分割率if (abs(k)<mins) {mins=abs(k);s1=i;s2=j;}//更優(yōu)解if (k<0) {i++;}else {j++;}//判斷加i還是加jwhile (a[j]==0) j++;//跳過所有0}printf("%.0lf\n%.0lf",a[s1],a[s2]);//輸出 }

總結

以上是生活随笔為你收集整理的vijos1237-隐形的翅膀【离散化】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。