frankchenfu 的博客

frankchenfu 的博客

题解 P1080 【国王游戏】

posted on 2018-10-02 22:36:36 | under 题解 |

我们先猜结论:$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. $1$在$2$正前方。
  2. $1$在$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}$$$$\begin{matrix}\because \frac{a_2}{b_1}<\frac{a_1}{b_2}\ ,\ a2\ge 1 \\ \therefore \frac{a_1}{b_2}>\frac{a_2}{b_1} \ge \frac{1}{b_1}.\\ \therefore ans_1= \frac{k\cdot a_1}{b_2} \end{matrix}$$

对于第二种,答案是$$\begin{matrix}ans_2=\max(\frac{k}{b_2},\frac{ka_2}{b_1})\\\\\begin{cases} \because a_1\ge1\\ \therefore \frac{k\cdot a_1}{b_2}\ge\frac{k}{b_2} \\\\ \because \frac{a_2}{b_1}<\frac{a_1}{b_2}\\ \therefore \frac{k\cdot a_1}{b_2}>\frac{ka_2}{b_1}\end{cases} \\\\\therefore ans_1\ge ans_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;
}