NOIP 國王遊戲 codevs1198 貪心+高精度

時空隧道

分析：

感覺這題的貪心比較不合常理，但是推一推還是可以推出來的…..主要是高精度難寫….

代碼如下：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=+;
int n,tmp[maxn],a[maxn],aa[maxn],MAX[maxn],f,maxlen,len;
char str[maxn];
struct M{
    int x,y,pro; 
    friend bool operator < (M a,M b){
        if(a.pro==b.pro)
            return a.y<b.y;
        return a.pro<b.pro;
    }
}s[maxn];
inline void mul(int a[],int b){
    memset(tmp,,sizeof(tmp));
    for(int i=;i<=len;i++)
        tmp[i]=a[i]*b;
    for(int i=;i<=len;i++)
        if(tmp[i]/)
            tmp[i+]+=tmp[i]/,tmp[i]%=;
    while(tmp[len+])
        len++;
    while(tmp[len]/)
        tmp[len+]+=tmp[len]/,tmp[len]%=,len++;
    for(int i=;i<=len;i++) 
        a[i]=tmp[i];
}
inline void div(int a[],int b){
    memset(tmp,,sizeof(tmp));
    int x=;
    for(int i=;i<=len;i++)
        tmp[i]=(a[i]+x*)/b,x=(a[i]+x*)%b;
    int pd=;
    for(int i=;i<=len;i++)
        if(tmp[i]){
            pd=;
            break;
        }
    if(pd){
        int i=;
        for(;tmp[i]==;i++);
        f=i;
        for(;i<=len;i++){
            if((tmp[i]>MAX[i]&&len-f+==maxlen)||len-f+>maxlen){
                for(int j=f;j<=len;j++)
                    MAX[j]=tmp[j];
                maxlen=len-f+;
                break;
            }
            if(maxlen>len-f+||tmp[i]<MAX[i])
                break;
        }
    }
}
signed main(void){
    scanf("%d",&n);
    for(int i=;i<=n;i++)
        scanf("%d%d",&s[i].x,&s[i].y),s[i].pro=s[i].x*s[i].y;
    sort(s+,s+n+);
    for(int i=;s[].x;i++)
        str[i]=s[].x%+'0',s[].x/=;
    len=strlen(str);
    for(int i=;i<=len;i++)
        a[i]=str[i-]-'0';
    for(int i=;i<=len;i++)
        aa[i]=str[len-i]-'0';
    for(int i=;i<=n;i++){
        div(aa,s[i].y),mul(a,s[i].x);
        for(int j=;j<=len;j++)
            aa[j]=a[len-j+];
    }
    for(int i=f;i<=maxlen+f-;i++)
        cout<<MAX[i];
    cout<<endl;
    return ;
} 
           

by >_< neighthorn