竞赛讨论区 > 能帮忙看看思路有问题吗?非高精度整数是60%我是70%通过率
头像
Wgaint
编辑于 2021-01-08 14:13
+ 关注

能帮忙看看思路有问题吗?非高精度整数是60%我是70%通过率

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2000;

int read()
{
    int x = 0,f = 1;char c = getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x = x * 10+ c - '0',c=getchar();}
    return x*f;
}

typedef struct bigint
{
        int d[maxn],len;
        void clean()    {       while(len>1 && !d[len-1])        len--;}

        bigint()        {memset(d,0,sizeof(d));         len=1;}
        bigint(int num)         {*this=num;}
        bigint operator = (const char* num)
        {
                len=strlen(num);
                for(int i=0;i<len;i++)  d[i]=num[len-1-i]-'0';
                clean();
                return *this;
        }
        bigint operator = (int num)
        {
                char s[maxn];
                sprintf(s,"%d",num);
                *this=s;
                return *this;
        }

        bigint operator + (const bigint& b)
        {
                bigint c=*this;
                int i;
                for(i=0;i<b.len;i++)
                {
                        c.d[i]+=b.d[i];
                        if(c.d[i]>9)    c.d[i]%=10,c.d[i+1]++;
                }
                while(c.d[i]>9)    c.d[i++]%=10,c.d[i]++;
                c.len=max(len,b.len);
                if(c.d[i] && c.len<=i)  c.len=i+1;
                return c;
        }

        bigint operator - (const bigint& b)
        {
                bigint c=*this;
                int i;
                for(i=0;i<b.len;i++)
                {
                        c.d[i]-=b.d[i];
                        if(c.d[i]<0)    c.d[i]+=10,c.d[i+1]--;
                }
                while(c.d[i]<0) c.d[i++]+=10,c.d[i]--;
                c.clean();
                return c;
        }

        bigint operator *(const bigint& b)const
        {
                int i,j;
                bigint c;
                c.len=len+b.len;
                for(j=0;j<b.len;j++)
                        for(i=0;i<len;i++)
                                c.d[i+j]+=d[i]*b.d[j];
                for(i=0;i<c.len-1;i++)
                        c.d[i+1]+=c.d[i]/10,c.d[i]%=10;
                c.clean();
                return c;
        }

        bigint operator /(const bigint& b)
        {
                int i,j;
                bigint c=*this,a=0;
                for(i=len-1;i>=0;i--)
                {
                        a=a*10+d[i];
                        for(j=0;j<10;j++)       if(a<b*(j+1))   break;
                        c.d[i]=j;
                        a=a-b*j;
                }
                c.clean();
                return c;
        }

        bigint operator % (const bigint& b)
        {
                int i,j;
                bigint a=0;
                for(i=len-1;i>=0;i--)
                {
                        a=a*10+d[i];
                         for(j=0;j<10;j++)       if(a<b*(j+1))   break;
                         a=a-b*j;
                }
                return a;
        }


        bool operator <(const bigint& b) const
        {
                if(len!=b.len)  return len<b.len;
                for(int i=len-1;i>=0;i--)
                        if(d[i]!=b.d[i])        return d[i]<b.d[i];
                return false;
        }

        bool operator >(const bigint& b) const        {return b<*this;}
        bool operator <=(const bigint& b) const {return !(b<*this);}
        bool operator >=(const bigint& b) const  {return !(*this<b);}
        bool operator !=(const bigint& b) const {return b<*this||*this<b;}
        bool operator ==(const bigint& b) const {return !(b!=*this);}

} bigint;

istream& operator >> (istream& in,bigint& x)
{
        string s;
        in>>s;
        x=s.c_str();
        return in;
}

ostream& operator <<(ostream& out,const bigint& x)
{
        out<<x.str();
        return out;
}


int cmp(pair<bigint, bigint> a,pair<bigint, bigint> b)
{
    return a.first*a.second<b.first*b.second;
}
int main()
{
    int n;
    cin>>n;
    pair<bigint, bigint> dacheng[n];
    bigint kingl,kingr;
    int x,y;
    x=read(),y=read();
    kingl=x,kingr=y;
    for(int i=0;i<n;i++)
    {
        x=read(),y=read();
        dacheng[i].first=x,dacheng[i].second=y;
    }
    sort(dacheng,dacheng+n,cmp);
    bigint max=kingl/dacheng[0].second;
    bigint tt=kingl;
    for(int i=1;i<n;i++)
    {
        tt*=dacheng[i-1].first;
        max=max>tt/dacheng[i].second?max:tt/dacheng[i].second;
    }
    cout<<max;
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐