国王游戏

AcWing-114-国王游戏

分析

见《进阶指南》第44页。

实现

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 1010;
struct node {
    int l, r;
    bool operator < (const node& o) const {
        return l * r < o.l * o.r;
    }
};
int n;
node a[N];

vector<int> mul (vector<int>& A, int b) {
    vector<int> C;
    int carry = 0;
    for (int i = 0; i < A.size() || carry != 0; ++ i) {
        if (i < A.size()) carry += A[i] * b;
        C.push_back(carry % 10);
        carry /= 10;
    }
    return C;
}
vector<int> div (vector<int>& A, int b) {
    vector<int> C;
    int r = 0;
    for (int i = A.size() - 1; i >= 0; -- i) {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
vector<int> max (vector<int> A, vector<int> B) {
    if (A.size() > B.size()) return A;
    if (A.size() < B.size()) return B;
    if (vector<int>(A.rbegin(), A.rend()) > vector<int>(B.rbegin(), B.rend())) return A;
    return B;
}

int main () {
    cin >> n;
    for (int i = 0; i <= n; ++ i) cin >> a[i].l >> a[i].r;

    sort(a + 1, a + n + 1);
    vector<int> res(1, 0), prod(1, 1);
    prod = mul(prod, a[0].l);
    for (int i = 1; i <= n; ++ i) {
        res = max(res, div(prod, a[i].r));
        prod = mul(prod, a[i].l);
    }

    for (int i = res.size() - 1; i >= 0; -- i)
        printf("%d", res[i]);
    return 0;
}