【NOIP2012 提高组 day1】国王游戏

题目

---

题解

–这是一道深深埋藏起来的贪心题
对于如下队列：
a0 b0
a1 b1
a2 b2
ans1=max(a0/b1,a0*a1/b2)

然而队列也可能是这样的：
a0 b0
a2 b2
a1 b1
ans2=max(a0/b2,a0*a2/b1)

因为 a0*a1/b2 > a0/b2 , a0*a2/b1 > a0/b1
所以说，要使ans1 < ans2
那么：a0*a1/b2 < a0*a2/b1
即：a1*b1 < a2*b2

所以贪心策略就出来了：a*b小的放在前面，sort一下就好啦

注意要写高精乘除低精度！

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=10005;

int n;
long long a[MAXN],b[MAXN];
long long c[MAXN];
int node[MAXN];

struct hehe
{
    long long A[MAXN];
    int l;

    hehe()
    {
        memset(A,0,sizeof(A));
        A[1]=1;
        l=1;
    }

    hehe operator *= (const long long &b)
    {
        for(int i=1; i<=l; i++)
            A[i]*=b;
        for(int i=1; i<=l; i++)
        {
            A[i+1]+=A[i]/10;
            A[i]%=10;
        }
        l++;
        while(A[l]>=10)
        {
            A[l+1]=A[l]/10;
            A[l]%=10;
            l++;
        }
        while(l>1&&!A[l])
            l--;
    }

    hehe operator / (const long long &b)
    {
        hehe c;
        c.l=l;
        long long left=0;
        for(int i=l; i>=1; i--)
        {
            left=left*10+A[i];
            c.A[i]=left/b;
            left%=b;
        }
        while(!c.A[c.l]&&c.l>1)
            c.l--;
        return c;
    }

    bool operator < (const hehe &b)const
    {
        if(l==b.l)
        {
            for(int i=l; i>=1; i--)
            {
                if(A[i]<b.A[i])
                    return 1;
                else if(A[i]>b.A[i])
                    return 0;
                else
                    continue;
            }
            return 0;
        }
        return l<b.l;
    }

} ans,now;

bool comp(const int &a,const int &b)
{
    return c[a]<c[b];
}

int main()
{
//  freopen("game.in","r",stdin);
//  freopen("game.out","w",stdout);
    cin>>n;
    cin>>a[0]>>b[0];
    for(int i=1; i<=n; i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        c[i]=a[i]*b[i];
        node[i]=i;
    }
    sort(node+1,node+1+n,comp);
    for(int i=1; i<=n; i++)
    {
        now*=a[node[i-1]];
        ans=max(ans,now/b[node[i]]);
    }
    for(int i=ans.l; i>=1; i--)
        printf("%lld",ans.A[i]);
    return 0;
}