做旅游网站的,凡科互动投票破解,各种网站制作,wordpress手写seo代码正题
题目链接#xff1a;https://vijos.org/p/1237 大意
有n支长度不一翅膀#xff0c;要求选择两只最接近黄金分割率的翅膀。 解题思路
暴力枚举O(n2)O(n2)是过不了的。
所有这就要用到离散了#xff0c;给翅膀长度排序。 然后一个i和一个j#xff0c;根据算出的比黄…正题
题目链接https://vijos.org/p/1237 大意
有n支长度不一翅膀要求选择两只最接近黄金分割率的翅膀。 解题思路
暴力枚举O(n2)O(n2)O(n^2)是过不了的。
所有这就要用到离散了给翅膀长度排序。 然后一个i和一个j根据算出的比黄金分割率大或小可以判断选择i和j那个需要增加翅膀。 时间复杂度O(nlogn)O(nlogn)O(nlogn) 代码
#includecstdio
#includealgorithm
using namespace std;
const double bl0.6180339887498949;//黄金分割率
int n,s1,s2;
double a[30001],k,mins;
double abs(double k)//abs
{if (k0) return -k;return k;
}
int main()
{scanf(%d,n);for (int i1;in;i)scanf(%lf,a[i]);sort(a1,a1n);int i1;int j2;mins2147483647;while (jn){ka[i]/a[j]-bl;//距离黄金分割率if (abs(k)mins) {minsabs(k);s1i;s2j;}//更优解if (k0) {i;}else {j;}//判断加i还是加jwhile (a[j]0) j;//跳过所有0}printf(%.0lf\n%.0lf,a[s1],a[s2]);//输出
}
