【NOIP2012 提高组 day1】国王游戏 题解

Boring__Zheng · 2019-07-16 19:34:05 · 题解

码量贼大，似乎我是c++题解里码量最少的？

这道题要求的是获得的最大金币数，那么我们可以推出最大的金币数 ans=a1 a2 a3 .... a(n+1)/aj/bj,至于为什么是n+1是因为还有一个国王，所以我们只需要找出一个i是得ai bi最大且i!=1（不能选国王） 然后运用高精度计算即可

代码：

#include<bits/stdc++.h>
using namespace std;
int v,Max,n,c,M,lenans，ans[40000001];
void MM(int x){
    for(int i=1;i<=lenans;i++) ans[i]*=x;
    for(int i=1;i<=lenans+15;i++) ans[i+1]+=ans[i]/10,ans[i]%=10;//15是因为最多进9位，所以就多算几位保险 
    for(int i=lenans+15;i>=lenans;i--)if(ans[i]!=0) lenans=i;
    return;
}
void cc(int x){
    int cnt=0;
    for(int i=lenans;i>=1;i--){
        cnt=cnt*10+ans[i]; 
        if(cnt<x) {ans[i]=0;continue;}
        ans[i]=cnt/x; cnt%=x;
    }
    for(int i=lenans;i>=1;i--) if(ans[i]!=0){ lenans=i; break;}
    return ;
}
int main(){
    cin>>n;
    ans[1]=1; lenans=1;
    for(int i=1;i<=n+1;i++){
        int a,b; cin>>a>>b;
        MM(a); v=a*b;
        if(v>Max&&i!=1) Max=v,c=b,M=a;
    }
    cc(M*c);
    if(ans[lenans]==0) ans[lenans]=1;//最少为1 
    for(int i=lenans;i>=1;i--) cout<<ans[i];
    return 0;
}