【大公鸡问题】百钱买百鸡（4）

大家好呀，这是百钱买百鸡系列的最后一篇啦，如果没看过之前文章的可以回顾一下百钱买百鸡（3），百钱买百鸡（2) ，百钱买百鸡

这次的题目如下

我们在上次说到本次的数据量比上次的多了10^10倍，于是我们将上次的代码修改如下

#include #include #include using namespace std;
int main(){    int n,c=0,xx=0,ii=0,l=0,j=0;    cin>>n;
        for(int i=n/4;i>=0 && j==0;i--)  //从多到少遍历母鸡的数量，这样可以保证公鸡数量尽量小，母鸡数量尽量大        {            if((n-4*i)%7==0)  //  因为这里只遍历了母鸡的数量，所以通过一个方向计算公鸡数量是否符合条件            {
                xx=(n-4*i)/7;  //xx为公鸡数量                ii=i;          //ii为母鸡数量                c=1;                j=1;            }

        }    while(true)    {        if(xx0 || ii0)        {            break;        }        xx+=4;        ii-=7;        l++;    }    if(c==0)    {        cout"No Answer.";    }    else    {        cout    }  return 0;
}

这里我们看到将主体的for循环部分删去了一个循环，这样时间复杂度得以降低为O（n），且不会导致while循环的少数问题，其余部分与百钱买百鸡（3）无异，本道题就解决啦

发表回复 取消回复

发表回复取消回复