首页 > 代码库 > AC日记——国王游戏 洛谷 P1080

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

国王游戏

 

思路:

  贪心+高精;

 

代码:

#include <bits/stdc++.h>using namespace std;#define maxn 1005struct 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[5000];    BintType operator*(const int pos)const    {        int i,p=0;        BintType res;        res.mem();        for(i=0;i<len;i++)        {            p+=(ch[i]-0)*pos;            res.ch[i]=p%10+0,p/=10;        }        while(p)        {            res.ch[i]=p%10+0;            p/=10,i++;        }        res.len=strlen(res.ch);        return res;    }    BintType operator/(const int pos)const    {        BintType res;        res.mem();        int i,p=0;        for(i=len-1;i>=0;i--)        {            p=p*10+ch[i]-0;            res.ch[i]=p/pos+0;            p%=pos;        }        res.len=strlen(res.ch);        for(int i=res.len-1;i>=0&&res.ch[i]==0;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-1;        while(i>=0&&ch[i]==pos.ch[i]) i--;        if(i<0) return false;        if(ch[i]<=pos.ch[i]) return true;        else return false;    }    void mem()    {        memset(ch,0,sizeof(ch)),len=0;    }    void print()    {        for(int i=len-1;i>=0;i--) putchar(ch[i]);    }};struct BintType ans,pos,temp;int n;inline void in(int &now){    char Cget=getchar();now=0;    while(Cget>9||Cget<0) Cget=getchar();    while(Cget>=0&&Cget<=9)    {        now=now*10+Cget-0;        Cget=getchar();    }}int main(){    in(n);    for(int i=0;i<=n;i++)in(ai[i].a),in(ai[i].b),ai[i].key=ai[i].a*ai[i].b;    sort(ai+1,ai+n+1);    ans.ch[0]=0,ans.len=1;    pos.ch[0]=1,pos.len=1;    for(int i=0;i<=n;i++)    {        temp=pos/ai[i].b;        if(ans<temp) ans=temp;        pos=pos*ai[i].a;    }    ans.print();    return 0;}

 

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