hdu 5620 KK's Steel（推理）

时间：2023-12-23 22:25:49
Problem Description
Our lovely KK has a difficult mathematical problem:he has a N(1≤N≤1018) meters steel,he will cut it into steels as many as possible,and he doesn't want any two of them be the same length or any three of them can form a triangle.
Input
The first line of the input file contains an integer T(1≤T≤10), which indicates the number of test cases.
Each test case contains one line including a integer N(1≤N≤1018),indicating the length of the steel.
Output
For each test case, output one line, an integer represent the maxiumum number of steels he can cut it into.
Sample Input
1
6
Sample Output
3
Hint

1+2+3=6 but 1+2=3 They are all different and cannot make a triangle.

Source
题意：
给你一个长度为N的钢管，问最多切成几个钢管，使得这些钢管不能围成三角形，并且不能有相同长度 ！
思路：
要想使得钢管尽量多，那肯定从1开始吧，有了1，且不能重复，那肯定找2吧，而且三个钢管不能围成，三角形，那直接找a1 + a2 = a3的情况不就恰好不能围成三角形吗。所以很明显，这是一个a1 = 1，a2 = 2的斐波那契数列，找到第一个i  是的前i项和大于N，即可！特殊判断N = 1，N=2即可！他们都是1！
 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<bitset>

 #include<map>

 #include<vector>

 #include<stdlib.h>

 using namespace std;

 #define ll long long

 #define eps 1e-10

 #define MOD 1000000007

 #define N 1000000

 #define inf 1e12

 ll n;

 ll f[N];

 void init(){

     f[]=;

     f[]=;

     for(ll i=;i<N;i++){

         f[i]=f[i-]+f[i-];

     }

 }

 int main()

 {

     init();

     int t;

     scanf("%d",&t);

     while(t--){

         scanf("%I64d",&n);

         ll sum=;

         ll i;

         for(i=;i<N;i++){

             sum+=f[i];

             if(sum>n){

                 break;

             }

         }

         if(n== || n==){

             printf("1\n");

             continue;

         }

         printf("%I64d\n",i-);

     }

     return ;

 }

相关文章