Fibonacci Sequence URAL – 1133(二分)

https://cn.vjudge.net/problem/URAL-1133
题目大意:一个数列满足斐波那契的性质,给你第i项和第j项的值让你推导出第n项的值来
思路:很裸的一道二分,只要二分枚举第i+1项的值然后判断就好了,但是依然卡了我半天。。。
主要问题是check函数里的for循环是从i+2开始跑的(第i项已知第i+1项由二分得来)那么当j等于i+1的时候就会出锅
输出时同理,当n小于i或n等于i或n等于i+1的时候没有考虑到,,粗心真可怕啊
代码

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

long long check(long long fi,long long ii,long long jj,long long mid,long long fj)
{
    long long ans=mid;
    for(int j=ii+2; j<=jj; j++)
    {
        ans=fi+mid;
        fi=mid;
        mid=ans;
        if(ans<-2e9)
        {
            return -1;
        }
        if(ans>2e9)
        {
            return 1;
        }
    }
    if(ans==fj)
    {
        return 0;
    }
    else if(ans>fj)
    {
        return 1;
    }
    else if(ans<fj)
    {
        return -1;
    }
}

int main()
{
    long long ii,fi,jj,fj,n;
    cin>>ii>>fi>>jj>>fj>>n;
    if(jj<ii)
    {
        swap(ii,jj);
        swap(fi,fj);
    }
    long long l=-2000000000,r=2000000000,mid,ans;
    while(l+1<r)
    {
        mid=(l+r)>>1;
        ans=check(fi,ii,jj,mid,fj);
        if(ans==0)
        {
            if(n==ii)
            {
                ans=fi;
            }
            else if(n==ii+1)
            {
                ans=mid;
            }
            else if(n<ii)
            {
                swap(mid,fi);
                for(int j=ii-1; j>=n; j--)
                {
                    ans=fi-mid;
                    fi=mid;
                    mid=ans;
                }
            }
            else
            {
                for(int j=ii+2; j<=n; j++)
                {
                    ans=fi+mid;
                    fi=mid;
                    mid=ans;
                }
            }
            cout<<ans<<endl;
            return 0;
        }
        else if(ans==1)
        {
            r=mid;
        }
        else if(ans==-1)
        {
            l=mid;
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注