AC日记——国王游戏 洛谷 P1080

国王游戏

思路：

　　贪心+高精；

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 1005

struct DataType {

    int a,b,key;

    bool operator<(const DataType pos)const

    {

        return key<pos.key;

    }

};

struct DataType ai[maxn];

struct BintType {

    int len;

    char ch[];

    BintType operator*(const int pos)const

    {

        int i,p=;

        BintType res;

        res.mem();

        for(i=;i<len;i++)

        {

            p+=(ch[i]-'')*pos;

            res.ch[i]=p%+'',p/=;

        }

        while(p)

        {

            res.ch[i]=p%+'';

            p/=,i++;

        }

        res.len=strlen(res.ch);

        return res;

    }

    BintType operator/(const int pos)const

    {

        BintType res;

        res.mem();

        int i,p=;

        for(i=len-;i>=;i--)

        {

            p=p*+ch[i]-'';

            res.ch[i]=p/pos+'';

            p%=pos;

        }

        res.len=strlen(res.ch);

        for(int i=res.len-;i>=&&res.ch[i]=='';i--,res.len--);

        return res;

    }

    bool operator<(const BintType pos)const

    {

        if(len<pos.len) return true;

        else if(len>pos.len) return false;

        int i=len-;

        while(i>=&&ch[i]==pos.ch[i]) i--;

        if(i<) return false;

        if(ch[i]<=pos.ch[i]) return true;

        else return false;

    }

    void mem()

    {

        memset(ch,,sizeof(ch)),len=;

    }

    void print()

    {

        for(int i=len-;i>=;i--) putchar(ch[i]);

    }

};

struct BintType ans,pos,temp;

int n;

inline void in(int &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

int main()

{

    in(n);

    for(int i=;i<=n;i++)in(ai[i].a),in(ai[i].b),ai[i].key=ai[i].a*ai[i].b;

    sort(ai+,ai+n+);

    ans.ch[]='',ans.len=;

    pos.ch[]='',pos.len=;

    for(int i=;i<=n;i++)

    {

        temp=pos/ai[i].b;

        if(ans<temp) ans=temp;

        pos=pos*ai[i].a;

    }

    ans.print();

    return ;

}