208012 - 国王游戏

题解bytianmeng

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<fstream> 
using namespace std;
int sum[50000],ans[50000],t[50000];//sum是每次到i这个人这里他左边所有人左手的乘积（排好序了的）
//ans是答案,t是一个临时数组，算一算每次sum除以右手的结果 ，并且与ans比比谁更大； 
int n;
struct node{
    int l,r,lr;
}pp[1009];//定义每个人，我这里将pp[0]算作国王； 
bool cmp(node x,node y){
    if(x.lr!=y.lr) return x.lr<y.lr;
    return x.r<y.r;
} //排序中的比大小 
void cheng(int x){
    for(int i=1;i<=sum[0];i++){
        sum[i]*=x;
}//因为是sum[i]里的数字是单精（因为买次都%了一下10），所以可以直接乘单精咯=。=

    int i;
    for(i=1;i<=sum[0];i++){
        sum[i+1]+=sum[i]/10;
        sum[i]%=10;//进位问题 
        if(i==sum[0] && sum[sum[0]+1]!=0) sum[0]++;//刚才高乘一直错就是在这里，写了一长串奇怪的东西。。清了清脑袋发现这里很容易，然后一串代码解决； 
    }
}
bool judge(){//判断t和ans谁大 
    for(int i=1;i<=t[0];i++){//为何比较要从i=1往后看下面solve就知道原因了，i才是最高位_(:зゝ∠)_ 
        if(t[i]!=ans[i]){
            return t[i]>ans[i];//巧妙的判断方法 
        }
    }
}
void solve(int x){
    int num=0,i=sum[0]+1,s=0;
    memset(t,0,sizeof(t));//初始化 
    while(num<x){
        --i;
        num=num*10+sum[i];//模拟数学中的除法，这也是为什么一开始i=sum[0]+1了，从高位开始取数嘛 
    }
    t[0]=i;//写个除法算式就看的懂了= =这个就是商的位数！ 
    for(;i>=1;i--){
        t[++s]=num/x;  //注意这里，你先放在前面的t[1],t[2]...都是数字里最大的数哦，跟sum里面不一样！ 
        num=num%x*10+sum[i-1];//继续算式模拟，算了数字之后把取mod的数*10再+下一位数，小学生都知道怎么算的除法 
    }
    if(t[0]>ans[0] || t[0]==ans[0] && judge()){
        for(int i=0;i<=t[0];i++)
        ans[i]=t[i];//公婆要和我比一比，比就比，谁怕谁谁怕谁
    }
}
int main(){
//    freopen("fxxk.in","r",stdin);
//    freopen("fxxk.out","w",stdout);
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        scanf("%d%d",&pp[i].l,&pp[i].r);
        pp[i].lr=pp[i].l*pp[i].r;
    }//cin;
    sum[1]=pp[0].l;//左手乘积的第一个就是国王的左手咯。 
    sum[0]=1;//位数先假装是1。。反正到时候会搞好的 
    ans[1]=0;//答案的第一位假装是0 
    ans[0]=1;//答案的位数先设定为1 
    sort(pp+1,pp+n+1,cmp);//compare;
    for(int i=1;i<=n;i++){
        cheng(pp[i].l);
        solve(pp[i].lr);
        //过程 
    }
    for(int i=1;i<=ans[0];i++)
    i<ans[0]?printf("%d",ans[i]):printf("%d\n",ans[i]);//i是最高位别忘了哦。。 
    return 0;
}