80分代码求助,测试点8和9RE
查看原帖
80分代码求助,测试点8和9RE
1637791
fengge_楼主2025/1/14 22:01
#include<bits/stdc++.h>
using namespace std;

int a[1010],t[100010],m[100010];
int la,lt,lm,n;
// la lt lm为操作数,用于操作数组和表示数组的长度,
// 他们的数值表示最大的下标
struct P{
    int a,b;
    bool operator <(const P &W)const{
        return a*b < W.a*W.b;
    }
}p[1010];

void mul(int m[],int b,int t[]){
    // 此时lt==lm 下面下标有所区别是为了增加可读性
    for (int i = 1;i <= lt;i++) t[i] = 0;
    for (int i = 1;i <= lm;i++) t[i] += m[i]*b;
    lm += 4;
    for (int i = 1;i < lm;i++){
        t[i+1] += t[i] / 10;
        t[i] %=10;
    }
    // 不用处理最高位的进位 
    // 因为若最高位不为0,lm自然会到那里
    while(t[lm] == 0&&lm > 1) lm--;
    for (int i = 1;i <=lm;i++) m[i] = t[i];
}

void div(int m[],int b,int t[]){
    for (int i = 1;i <= lt;i++) t[i]=0; // ?
    int r = 0;
    for (int i = lm;i>=1;i--){
        r = r*10 + m[i];
        t[i] = r/b;
        r %=b;
    }
    lt = lm;
    while(t[lt] == 0 && lt > 1) lt--;
}

bool cmp(int a[],int t[]){
    if (lt != la) return la < lt;
    else {
        // 此时lt==lm <lt或<lm都可以
        for (int i = lt;i;i--)
            if (t[i] != a[i]) return a[i]<t[i];
        return false;
    }
}

void upd(int a[],int t[]){
    if (cmp(a,t)) {
        for (int i = lt;i >=1;i--) a[i] = t[i];
        la = lt;
    }
}


int main(){
    cin >> n;
    for (int i = 0;i <= n;i++){
        cin >> p[i].a >> p[i].b;
    }
    sort(p+1,p+n+1);
    m[++lm] = p[0].a;
    for (int i = 1;i <= n;i++){
        div(m,p[i].b,t);
        upd(a,t);
        mul(m,p[i].a,t);
    }
    for (int i = la;i;i--) cout << a[i];
}
2025/1/14 22:01
加载中...