P1080 国王游戏

· · 题解

P1080 国王游戏King Game

原题链接

洛谷 P1080

题目大意

有一位国王和n位大臣，每个大臣及国王左(l)右(r)手上面分别有一个整数。让这n位大臣排成一排，国王站在队伍的最前面。第i位大臣获得的金币数是前i-1位大臣左手(l)的乘积除以第i位大臣右手(r)上的数字。

由于这个国王比较小气， 你要求出一种排列方式，使得获得奖赏最多的大臣获得的金币数最小。

思路分析

既然国王这么小气，那这道题的正解必然就是贪心了。

接下来我们来一句一句话来拆解题干并通过代码实现。

公式简化推导：

我们可以发现每个式子里都有S,而S我们每次又不可能现推，所以我们需要将S消掉，让每个式子都乘a.r*b,r/S,这样，原式子就成了max(b.r,a.r*a.l)<max(a.r,b.r*b.l)

到这里，您是不是认为已经挺简单的了？NO！！！还可以把max这个函数去掉。我们这么想：如果b.r为式子一中的最大值，也就是说b.r>a.r*a.l，自然地，b.r>a.r，所以式子二的返回值就是b.r*b.l,此时式子二一定是大于式子一的，所以cmp比较器里返回a.r*a.l<b.r*b.l即可。

至此，此题思路已讲解完毕，但如果你自信地把这份代码交了上去，发现竟然只得了60pts！！！此时你默默地点击了“下载数据”，发现：这么长的数！！！，看数据约束可以发现最大值竟然可以达到 10000^{1000}！！！所以说，可以用（bi xu yong)我们最喜欢 （zui tao yan） 的高精度才能AC！

#include<bits/stdc++.h>
using namespace std;
int n;
struct Person{
    int l,r; 
}p[1005];
//p[0]为国王，p[1]~p[n]为大臣 
bool cmp(Person a,Person b){
    return a.r*a.l<b.r*b.l;//根据推导的公式比较 
} 
int s[4005],d[4005],ans[4005]; 
int LEN=4004;
void cheng(int x){//高精度*单精度 
    for(int i=1;i<=LEN;i++) s[i]=s[i]*x;//进位
    for(int i=1;i<=LEN;i++){
        s[i+1]+=s[i]/10;
        s[i]%=10;
    } 
}
void chu(int x){//高精度/单精度 
    //从s最高位开始除 
    memset(d,0,sizeof(d));
    int r=0;//余数 
    for(int i=LEN;i>=1;i--){
        r=r*10+s[i];//当前的被除数
        d[i]=r/x;
        r=r%x; 
    } 
} 
bool f(){
    //比较的是ans和d数组 
    for(int i=LEN;i>=1;i--){
        if(ans[i]>d[i]) return false;
        if(ans[i]<d[i]) return true;
    }
    return false;
} 
void cpy(){
    //把d赋值给ans 
    for(int i=1;i<=LEN;i++) ans[i]=d[i];
} 
void print(){
    //输出ans数组 
    while(ans[LEN]==0&&LEN>1) LEN--;//去前导0
    for(int i=LEN;i>=1;i--) cout<<ans[i]; 
}

int main(){
    cin>>n;
    for(int i=0;i<=n;i++) 
        cin>>p[i].l>>p[i].r;//输入国王及大臣左右手上的数 
    sort(p+1,p+n+1,cmp);//根据推导公式排序 
    s[1]=1; 
    for(int i=1;i<=n;i++){
        cheng(p[i-1].l); //前i-1个大臣左手的乘积
        //高精度乘 s[] 
        chu(p[i].r);//第i个大臣能获得的奖赏 
        //高精度除 d[] 
        if(f()) cpy();
        //高精度比较&&高精度赋值 
    }
    print();//输出答案 
    return 0;
}

THE END.

THANK YOU.