洛谷P1080(NOIP2012)国王游戏——贪心排序与高精度

题目：https://www.luogu.org/problemnew/show/P1080

排序方法的确定，只需任取两个人，通过比较与推导，可以得出ai*bi小的人排在前面；

高精度写的时候犯了些细节错误，详见注释。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define MAXN 200005

using namespace std;

typedef long long ll;//用long long!

ll n,ka,kb,ans[MAXN],tmp[MAXN],tmp2[MAXN],c[MAXN];

struct N{

    ll a,b;

}p[];

bool cmp(N x,N y)

{

    return x.a*x.b<y.a*y.b;

}

void chu(ll a[],ll b)

{

    ll x=;

    c[]=a[];

    for(ll i=a[];i>;i--)//倒序存储，正序除

    {

        c[i]=(x*+a[i])/b;

        x=(x*+a[i])%b;

    }

    while(c[c[]]==&&c[]>)c[]--;

}

void ch(ll a[],ll b)

{

    ll x=;

    for(ll i=;i<=a[];i++)//倒序乘

    {

        a[i]*=b;a[i]+=x;

        x=a[i]/;

        a[i]%=;

    }

    while(x)a[]++,a[a[]]=x%,x/=;

}

int com(ll a[],ll b[])

{

    if(a[]>b[])return ;

    if(a[]<b[])return -;

    for(ll i=a[];i;i--)//倒序！

        if(a[i]>b[i])return ;

    return ;

}

void print(ll a[])

{

//    if(a[a[0]]==0)//?

//    {

//        printf("1");

//        return;

//    }

    printf("%lld",a[a[]]);

    for(ll i=a[]-;i>;i--)

    {

        printf("%lld",a[i]/);

        a[i]%=;

        printf("%lld",a[i]/);

        a[i]%=;

        printf("%lld",a[i]/);

        a[i]%=;

        printf("%lld",a[i]);

    }

}

int main()

{

    scanf("%lld%lld%lld",&n,&ka,&kb);

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

        scanf("%d%d",&p[i].a,&p[i].b);

    sort(p+,p+n+,cmp);

    tmp[]=;tmp[]=ka;//压位

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

    {

        memcpy(tmp2,tmp,sizeof tmp);

        memset(c,,sizeof c);

        chu(tmp2,p[i].b);

        if(com(c,ans)>)memcpy(ans,c,sizeof c);//必须>0，否则-1也会被算！

        ch(tmp,p[i].a);

    }

    print(ans);

    return ;

}

这个运行起来有点慢，有些地方写得不够好，下面有一篇运行很快的代码，可以比较看看提速的方法。

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

using namespace std;

const int INF=;

typedef long long ll;

ll n,gb,ljc[],max,tmp[],ans[];

char tp[];

struct Node{

    ll a,b,w;

}r[];

bool cmp(Node x,Node y)

{

    return x.w<y.w;

}

void chu(ll b)

{

    ll x=;

    tmp[]=ljc[];

    for(ll i=ljc[];i;i--)

    {

        ll s=ljc[i]+x*INF;

        tmp[i]=s/b;

        x=s%b;

    }

    while(!tmp[tmp[]]&&tmp[]>)tmp[]--;

}

bool comp(ll ans[],ll b[])

{

    if(ans[]>b[])return ;

    if(ans[]<b[])return ;

    for(ll i=ans[];i;i--)

    {

        if(ans[i]>b[i])return ;

        if(ans[i]<b[i])return ;

    }

    return ;

}

void mul(ll a)

{

    ll x=;

    for(ll i=;i<=ljc[];i++)

    {

        ll s=ljc[i]*a+x;

        x=s/INF;

        ljc[i]=s%INF;

    }

    if(x)ljc[]++,ljc[ljc[]]=x;//至多进一位

}

int main()

{

    scanf("%lld%lld%lld",&n,&ljc[],&gb);

    ljc[]=;

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

    {

        scanf("%lld%lld",&r[i].a,&r[i].b);

        r[i].w=r[i].a*r[i].b;

    }

    sort(r+,r+n+,cmp);

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

    {

        memset(tmp,,sizeof tmp);

        chu(r[i].b);

        if(comp(ans,tmp))memcpy(ans,tmp,sizeof tmp);

        mul(r[i].a);

    }

    printf("%lld",ans[ans[]]);

    for(ll i=ans[]-;i;i--)

    {

        printf("%lld",ans[i]/);

        printf("%lld",ans[i]/%);

        printf("%lld",ans[i]/%);

        printf("%lld",ans[i]%);

    }

    return ;

}

巴特西

洛谷P1080(NOIP2012)国王游戏——贪心排序与高精度

最新文章

热门文章