题解 P1080 【国王游戏】

frankchenfu · 2018-10-02 22:36:36 · 题解

我们先猜结论：a_i小的排前面，那么后面的人乘积就比较小；b_i小的排前面，那么后面b_i较大，商就小……所以和a_i,b_i都有关系，那么这时候（如果可以贪心）一般就是a_ib_i排序、a+b、a-b三种排序方法。我们简单的算一下，发现有可能是a_ib_i，那么就尝试证明一下。

不妨设两个人分别写了a_1,b_1,a_2,b_2且满足a_1b_1>a_2b_2，则有\frac{a_2}{b_1}<\frac{a_1}{b_2}。

有以下2种情况：

设在1、2之前所有人左手乘积为k，那么

对于第一种，我们的答案就是\begin{matrix}ans_1&=&\max(\frac{k}{b_1},\frac{ka_1}{b_2})\\ &=& k\cdot \max(\frac{1}{b_1},\frac{a_1}{b_2})\end{matrix}

对于第二种，答案是

换句话说，当我们分析了第二种情况后发现，无论是第1个人还是第2个人拿的钱数都一定比第一种中第2个人拿的钱数少。

因此，我们得出结论：如果a_ib_i<a_jb_j，那么应当让i排在j的前方，即按照a_ib_i的大小从小到大排序。

于是我们可以贪心解决，但是注意到对于100\%的数据有1\le n\le1000,0<a,b<10000，因此我们需要使用高精度。这里写高精度非常的方便，不需要用到板子：因为所有的a,b不超过10^4，所以我们可以压4位，模数取10^4；乘法不会溢出，可以直接使用int。乘除法都是高精乘/除低精，都可以直接逐位处理……最让人感动的就是除法了，特别好写。感觉print()函数的写法是有技巧的，看楼下的题解似乎什么都好，就是print()函数写的很臃肿。

说明：高精虽然封装了但是也只是习惯，事实上是我模拟赛打这题的时候花了\text{30min}手打的。

下面给出代码（高精封装）：

#include<cstdio>
#include<cstring>
#include<algorithm>
const int MAXN=1010;

struct bign{
    const int BASE=1e4;
    int a[MAXN<<2],len;
    bign(int len=0){
        this->len=len;
    }
    bign operator=(int rhs){
        len=0;
        if(rhs==0){
            len=1;
            return *this;
        }
        while(rhs){
            a[++len]=rhs%BASE;
            rhs/=BASE;
        }
        return *this;
    }
    bign operator=(const bign rhs){
        memcpy(a,rhs.a,sizeof(rhs.a));
        len=rhs.len;
        return *this;
    }
    void operator*=(const int rhs){
        for(int i=1;i<=len;i++)
            a[i]*=rhs;
        for(int i=1;i<=len;i++){
            a[i+1]+=a[i]/BASE;
            a[i]%=BASE;
            if(i+1>len&&a[i+1])
                len++;
        }
        while(len&&a[len]==0)
            len--;
    }
    bign operator/(const int rhs){
        bign c;c=*this;
        while(c.len&&c.a[c.len]==0)
            c.len--;
        for(int i=c.len;i;i--){
            c.a[i-1]+=(c.a[i]%rhs)*BASE;
            c.a[i]/=rhs;
        }
        while(c.len&&c.a[c.len]==0)
            c.len--;
        return c;
    }
    void print(){
        while(len&&a[len]==0)
            len--;
        if(len==0){
            putchar('0');
            return;
        }
        printf("%d",a[len]);
        for(int i=len-1;i;i--)
            printf("%04d",a[i]);
    }
    bool operator>(const bign &rhs)const{
        if(len!=rhs.len)
            return len>rhs.len;
        for(int i=len;i;i--)
            if(a[i]!=rhs.a[i])
                return a[i]>rhs.a[i];
        return 0;
    }
}mul,ans;

struct node{
    int a,b;
    bool operator<(const node &rhs)const{
        return a*b<rhs.a*rhs.b||(a*b==rhs.a*rhs.b&&a<rhs.a);
    }
}p[MAXN];

int main(){
//  freopen("game.in","r",stdin);
//  freopen("game.out","w",stdout);
    int n;scanf("%d",&n);
    for(int i=0;i<=n;i++)
        scanf("%d%d",&p[i].a,&p[i].b);
    std::sort(p+1,p+n+1);
    mul=p[0].a;
    for(int i=1;i<=n;i++){
        bign tmp=mul/p[i].b;
        if(tmp>ans)
            ans=tmp;
        mul*=p[i].a;
    }
    ans.print();
    return 0;
}