没看清题面,不小心写了个高精除..不想改低精..
查看原帖
没看清题面,不小心写了个高精除..不想改低精..
47425
clarkwang楼主2022/10/9 22:35

代码很长...

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define M 100000000

using namespace std;

struct Number {
    long long d[10001], l;
    Number() {
        memset(d, 0, sizeof(d));
        l = 0;
    }
    Number(int x) {
        l = 0;
        while(x) {
            d[++l] = x % M;
            x /= M;
        }
    }
    void print(int end = 0) {
        printf("%lld", d[l]);
        for(int i = l - 1;i;i--) {
            printf("%08lld", d[i]);
        }
        if(end == 1) {
            printf(" ");
        }
        if(end == 2) {
            printf("\n");
        }
    }
    friend bool operator < (Number A, Number B) {
        if(A.l < B.l) {
            return true;
        } else if(A.l > B.l) {
            return false;
        }
        for(int i = A.l;i;i--) {
            if(A.d[i] < B.d[i]) {
                return true;
            }
            if(A.d[i] > B.d[i]) {
                return false;
            }
        }
        return false;
    }
    friend Number operator + (Number A, Number B) {
        Number C = Number();
        long long l = max(A.l, B.l), t = 0;
        for(int i = 1;i <= l;i++) {
            C.d[i] = (A.d[i] + B.d[i] + t) % M;
            t = (A.d[i] + B.d[i] + t) / M;
        }
        C.l = l;
        if(t) {
            C.d[++C.l] = t;
        }
        return C;
    }
    friend Number operator * (Number A, Number B) {
        Number C = Number();
        C.l = A.l + B.l - 1;
        for(int i = 1;i <= A.l;i++) {
            for(int j = 1;j <= B.l;j++) {
                C.d[i + j - 1] += A.d[i] * B.d[j];
            }
        }
        for(int i = 1;i < C.l;i++) {
            C.d[i + 1] += C.d[i] / M;
            C.d[i] %= M;
        }
        while(C.d[C.l] >= M) {
            C.d[C.l + 1] = C.d[C.l] / M;
            C.d[C.l] %= M;
            C.l++;
        }
        return C;
    }
    friend Number operator - (Number A, Number B) {
        Number C = Number();
        long long l = max(A.l, B.l), t = 0;
        for(int i = 1;i <= l;i++) {
            C.d[i] = (A.d[i] - B.d[i] + t + M) % M;
            t = (A.d[i] - B.d[i] + t - M + 1) / M;
            if(C.d[i]) {
                C.l = i;
            }
        }
        if(t) {
            return Number();//负数
        }
        return C;
    }
    friend Number operator / (Number A, Number B) {
        Number C = Number();
        while(!(A < B)) {
            Number K = B, D = 1;
            while(!(A < K * 10)) {
                K = K * 10;
                D = D * 10;
            }
            while(!(A < K)) {
                A = A - K;
                C = C + D;
            }
        }
        return C;
    }
};

struct Player {
    int a, b;
    Player(int x = 0, int y = 0):a(x), b(y) {}
    friend bool operator < (Player A, Player B) {
        return ((A.a * A.b) < (B.a * B.b));
    }
} P[10001];

int n;

int main() {
    scanf("%d", &n);
    for(int i = 0;i <= n;i++) {
        scanf("%d%d", &P[i].a, &P[i].b);
    }
    sort(P + 1, P + n + 1);
    Number ans = Number(0);
    Number mul = Number(1);
    for(int i = 1;i <= n;i++) {
        mul = mul * Number(P[i - 1].a);
        Number k = mul / Number(P[i].b);
        if(ans < k) {
            ans = k;
        }
    }
    ans.print(2);
    return 0;
}

还有优化空间吗...现在卡了#6#8#9#10TLE过不去
希望有方法不重写低精除,因为比较懒

2022/10/9 22:35
加载中...