HDOJ 5620-KK's Steel【斐波那契数列】

╰半橙微兮° 2022-08-20 15:16 87阅读 0赞

# KK's Steel #

# Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)  Total Submission(s): 505 Accepted Submission(s): 242 #

Problem Description

Our lovely KK has a difficult mathematical problem:he has a  N(1≤N≤10![Image 1][]18![Image 1][])![Image 1][] 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)![Image 1][], which indicates the number of test cases.  
  
Each test case contains one line including a integer  N(1≤N≤10![Image 1][]18![Image 1][])![Image 1][],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

[BestCoder Round \#71 (div.2)][BestCoder Round _71 _div.2]

解题思路：

原来做过一道一样的，只不过没要求每根都不一样，这道题要求了，果断wa了一次，主要还是考虑不能构成三角形，就是斐波那契数列。

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    long long map[100000];
    int main()
    {
    	int T;
    	scanf("%d",&T);
    	map[0]=1;
    	map[1]=1;
    	long long i,j=1;
    	for(;;)
    	{
    		j++;
    		map[j]=map[j-1]+map[j-2];
    		if(map[j]>1e18)
    		break;
    	}
    	for(i=2;i<=j;i++)
    	{
    		map[i]+=map[i-1];
    	}
    	while(T--)
    	{
    		long long L;
    		scanf("%lld",&L);
    		int ans=1;
    		if(L==1)
    		{
    			printf("1\n");
    			continue;
    		}
    		if(L==2)
    		{
    			printf("1\n");
    			continue;
    		}
    		for(;;)
    		{
    			if(map[ans]==L)
    			{
    				printf("%d\n",ans);
    				break;
    			}
    			else if(map[ans]>L)
    			{
    				printf("%d\n",ans-1);
    				break;
    			}
    			ans++;
    		}
    		//printf("%d\n",ans-1);
    	}
    	return 0;
    }

[Image 1]: 
[BestCoder Round _71 _div.2]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2371+%28div.2%29&source=1&searchmode=source