60求调,写了高精还是wa#5#7#8#9
查看原帖
60求调,写了高精还是wa#5#7#8#9
1460508
tank737楼主2024/10/30 19:32
#include<iostream>
#include<algorithm>
using namespace std;
struct dachen{
    int l,r,ans[10000]={0},len=0;
}dc[1010];
bool cmp(dachen a,dachen b){
    return a.l*a.r<b.l*b.r;
}
int main(){
    int n,len=0,h[10000]={1},as=0;
    cin>>n>>dc[0].l>>dc[0].r;
    for(int i=1;i<=n;i++)cin>>dc[i].l>>dc[i].r;
    sort(dc+1,dc+n+1,cmp);
    for(int i=0;i<n;i++){
        int x=dc[i].l,p=0,k[100]={0};
        while(x>0){//转化数字为高精
            k[p++]=x%10;
            x/=10;
        }
        p--;
        for(int j=0;j<=len;j++){//高精乘高精
            for(int o=0;o<=p;o++){
                dc[i+1].ans[j+o]=h[j]*k[o];
            }
        }
        len+=p;
        for(int j=0;j<=len;j++){//十进制处理
            if(dc[i+1].ans[j]>9){
                dc[i+1].ans[j+1]+=dc[i+1].ans[j]/10;
                dc[i+1].ans[j]%=10;
                if(j==len)len++;
            }
        }
        while(dc[i+1].ans[len]==0)len--;//去前导零,感觉我这么写可以不用去0
        for(int j=0;j<=len;j++){//转移答案
            h[j]=dc[i+1].ans[j];
        }
        int kh=0;
        for(int j=len;j>=0;j--){//高精除以低精
            kh=kh*10+dc[i+1].ans[j];
            if(kh/dc[i+1].r!=0){
                dc[i+1].ans[j]=kh/dc[i+1].r;
                kh%=dc[i+1].r;
                dc[i+1].len=max(j,dc[i+1].len);
            }
            else dc[i+1].ans[j]=0;
        }
        if(dc[as].len!=dc[i+1].len){//比较最大
            if(dc[as].len<dc[i+1].len)
                as=i+1;
        }
        else{
            for(int j=dc[as].len;j>=0;j--){
                if(dc[as].ans[j]<dc[i+1].ans[j]){
                    as=i+1;
                    break;
                }
            }
        }
    }
    for(int j=dc[as].len;j>=0;j--)cout<<dc[as].ans[j];
    return 0;
}
2024/10/30 19:32
加载中...