题解 | #至至子的斐波那契#

C

至至子的斐波那契

题意：

至至子会进行 TT 次询问，每次询问给定一个数 a[i]，他想让你找到斐波那契数列中距离a[i] 最近的一项，即求一个正整数 x 使得在满足 |F[x] - a[i]| 最小的基础上 xx 尽量小。

首先：先把斐波那契数列求出来：

f[1]=1,f[2]=1;
for(long long i=3;i<=n;i++)
{
  	f[i]=f[i-1]+f[i-2];
}

运用到二分

#include<bits/stdc++.h>
using namespace std;
long long t;
const long long n=90;
long long f[100];
long long a;
int main()
{
	f[1]=1,f[2]=1;
	for(long long i=3;i<=n;i++)
	{
		f[i]=f[i-1]+f[i-2];
	}
	cin>>t;
	while(t--)
	{
		cin>>a;
		long long pos=lower_bound(f+1,f+n+1,a)-f;
		printf("%lld\n",abs(f[pos]-a)<abs(f[pos-1]-a)?pos:pos-1);//19行
	}
	return 0;
}

19行：比较相邻两个的远近，

注意：距离相等，取下标更小的