哈理工第十届程序设计竞赛 F 三角形 题解

题目大意

小明有一根长度为a的木棒，现在小明想将木棒分为多段（每段木棒长度必须为整数），
使得分隔后的木棍中，取出的任意三段都不能构成三角形，小明想知道木棒最多被分成几段？

解题思路

由斐波那契数列得到，最佳的情况是每一段长度由斐波那契数列构成的。

因为斐波那契数列刚好是$a+b=c$，所以都不能构成三角形。

（可能这世界上就我不知道了吧。。

那我只需要构造出一个斐波那契数列的前缀和数组。

对这个数组进行二分查找即可。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

double n[200];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	double c = 1, cq = 1;
	n[1] = 1, n[2] = 2;
	for (int i = 3; i <= 150; i++) {
		n[i] = n[i - 1] + c+cq;
		swap(c, cq);
		c += cq;
	}
	while (t--) {
		double a;
		cin >> a;
		int pos = upper_bound(n + 1, n + 150, a) - n;
		pos--;
		cout << pos << endl;
	}
}