蓝桥杯2016年第七届真题-最大比例-题解（C++代码）

解题思路:

       1.求等比数列最大的公比，而且题目给出的数据保证有解，一开始考虑等比数列的求和公式啥的，但是对解决题目好像没什么用。               

       2.然后想到等比数列的定义，a_n =  a₁ * q^n-1 , 是不是可以把每两个数据的商求出来，消去了a₁ ， 得到了一个集合{  qⁱ  |  i  >=  1 }。

       3.对数据的初步处理解决了，现在问题变成了如何从一些 qⁱ  中获得最大的公比呢？

       4.每次从已有的{ qⁱ  }集合中找一个未使用过，且 i 最大的qⁱ    ,让其与剩下所有（比它小）的相除，如果获得了新的 qⁱ , 加入到集合中。              

       5.当所有 qⁱ 都已经使用过后，集合中最小的元素就是 最大的公比。              

注意事项:              

           求 集合 { qⁱ } 前已经对数组升序、去重处理，所以得到的 qⁱ 都是严格大于1的。             

           所以如果 qⁱ  > q^j ,那么 qⁱ 的分子会比q^j 大，而分母也同样如此，但是如果q 是整数的话分母会同为1。

参考代码:

                思路大概就如上所述，代码写得比较糙，仅供参考，O(∩_∩)O哈哈~

#include using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
    return b == 0 ? a:gcd(b,a%b);
}
struct node
{
    ll a,b;
    node(ll a,ll b):a(a),b(b){}
    node(){}
    bool operator (double)((double)t.a/(double)t.b);
    }
    bool operator == (const node&t)const
    {
        return  (double)((double)a/(double)b) == (double)((double)t.a/(double)t.b);
    }
};
int main(){
    int n;
    cin>>n;
    ll a;
    set se;
    vector ve;
    for(int i = 1;i>a;
        if(!se.count(a)) 
        {
            se.insert(a);
            ve.push_back(a);
        }    
    }
    sort(ve.begin(),ve.end());
    
    set fe;
    vector vf;
    for(int i = 0;i<ve.size()-1;i++)
    {
        ll p = gcd(ve[i+1],ve[i]);
        fe.insert(node(ve[i+1]/p,ve[i]/p));
    }
    queue q;
    bool flag = true;
    int kcase = 0;
    while(1)
    {
        vf.clear();
        for(set::iterator it = fe.begin();it!=fe.end();it++)
        {
            vf.push_back(*it);
        }
        sort(vf.begin(),vf.end());
//    reverse(vf.begin(),vf.end());
        if(!flag)
        {
    //        break;
        } 
        flag = false;
        for(int i = kcase++;i= vf.size()){
            break;
        }
        node t = q.front();
        q.pop();
    //    cout<<t.a<<' '<<t.b<<endl<<endl;
        while(!q.empty())
            {
                node tem = q.front();
                q.pop();
        //        if(tem==t) continue;
                node now = node(t.a / tem.a,t.b/tem.b);
        //    cout<<now.a<<' '<<now.b<<endl;
                if(fe.count(now))
                {
                    continue;
                }
                else
                {
                    flag = true;
                    fe.insert(now);
                }
            }
    }
    
    cout<<vf[vf.size()-1].a<<'/'<<vf[vf.size()-1].b<<endl;
    return 0;
}