题解 P1080 【国王游戏】

· · 题解

看到这题标签：贪心。于是就想：怎么贪呢？

贪心

这道题70多行代码，其中的贪心只有5行，但这却是本题最难的部分。

开始推导：假设已经排了几个人（包括国王），设他们左手上的数的乘积为S。

现在要给2个人排序，记第一个人左手上的数为a_{1}，右手上的数为b_{1}；第二个人左手上的数为a_{2}，右手上的数为b_{2}。

如果第一个人排在前面优于第二个人排在前面，那么

max(S/b_{1},S*a_{1}/b_{2}) < max(S/b_{2},S*a_{2}/b_{2})

而又由于a_{1},b_{1},a_{2},b_{2},S>0，所以 S/b_{2} ≤ S*a_{1}/b_{2}。

假设S*a_{1}/b_{2}≥S*a_{2}/b_{1}，则显然max(S/b_{1},S*a_{1}/b_{2})≥max(S/b_{2},S*a_{2}/b_{1})，矛盾。

所以S*a_{1}/b_{2}<S*a_{2}/b_{1}=>a_{1}*b_{1}<a_{2}*b_{2}

只需将数组*按照$ab$从小到大排序**即可。

高精度

这道题高精还是挺复杂的。

本题需要支持复制、比较、乘、除4种高精度操作（当然也有输出）。

  1. 复制：没什么好说的，一位一位赋值就好了。

  2. 比较：也没什么好说的，从高位到低位比较即可，注意是bool类型。

  3. 乘法：注意先从高到低乘一遍，再从低到高进位。

  4. 除法：要用一个数记录，和快读差不多。

代码

相信你们都会看到这里。。。

附上代码——

#include<cstdio>
#include<algorithm>//用到sort
#include<cstring>//用到memset
using namespace std;
const int MAXN=1010,MAXM=10010;//注意高精数组开到10000
struct Node{//一个人
    int l,r;
}a[MAXN];
int pro[MAXM],ans[MAXM],tmp[MAXM];//左手乘积，答案，临时数组
int read(){//快读
    int x=0,f=1;//记录数和符号
    char c=getchar();//读入字符
    while(c<'0'||c>'9'){//只要不是数
        if(c=='-') f=-1;//是负号就记录
        c=getchar();
    }
    while(c>='0'&&c<='9'){//只要是数
        x=x*10+c-'0';//挪位再加
        c=getchar();
    }
    return x*f;//返回数乘符号
}
bool cmp(Node aa,Node bb){//排序的比较函数
    return aa.l*aa.r<bb.l*bb.r;//按左右手数的乘积从小到大
}
void copy(int *aa,int *bb){//复制
    for(int i=0;i<MAXM;i++) aa[i]=bb[i];
}
bool more(int *aa,int *bb){//比较
    for(int i=MAXM-1;i>=0;i--){
        if(aa[i]>bb[i]) return 1;
        if(aa[i]<bb[i]) return 0;
    }
    return 0;//注意这里也要写上，写0写1随便
}
void times(int *aa,int num){//乘法
    for(int i=MAXM-2;i>=0;i--) aa[i]*=num;//先乘
    for(int i=0;i<MAXM-1;i++){//再进位
        aa[i+1]+=(aa[i]/10);//先加前一位
        aa[i]%=10;//在处理这一位
    }
}
void div(int *aa,int *bb,int num){//除法
    memset(bb,0,sizeof(bb));//赋为0
    int x=0;
    for(int i=MAXM-1;i>=0;i--){//从高位到低位
        x=x*10+aa[i];//挪位再加
        bb[i]=x/num;//记录
        x%=num;//模上
    }
}
void print(int *aa){//输出
    bool flag=0;//记录是否能输出
    for(int i=MAXM-1;i>=0;i--){
        if(!flag){//如果不能
            if(aa[i]) flag=1;//找到第一个不是0的位，可以输出了
            else continue;//还是不能
        }
        printf("%d",aa[i]);//输出，不用空格或换行
    }
}
int main(){//主函数
    int n=read();
    for(int i=0;i<=n;i++) a[i].l=read(),a[i].r=read();
    sort(a+1,a+n+1,cmp);//排序
    pro[0]=1;//注意乘积数组初始值为1
    for(int i=0;i<=n;i++){//注意从0开始，国王
        div(pro,tmp,a[i].r);//先除到tmp上
        if(more(tmp,ans)) copy(ans,tmp);//比较，满足就复制
        times(pro,a[i].l);//自乘
    }
    print(ans);//输出
    return 0;//华丽结束
}

看我这么辛苦写的一篇题解，总要点个赞再走呀~