60分,求大佬调
查看原帖
60分,求大佬调
1368915
yejiacheng楼主2025/8/3 16:53
#include<bits/stdc++.h>
using namespace std;
struct Minister {
    int a;  // 左手的数
    int b;  // 右手的数
};
// 排序规则:按 a*b 从小到大排序
bool compare(const Minister &m1, const Minister &m2) {
    return (long long)m1.a * m1.b < (long long)m2.a * m2.b;
}
// 高精度乘法:大整数(用vector存储,低位在前)乘以小整数
vector<int> multiply(const vector<int> &num, int x) {
    vector<int> res;
    int carry = 0;
    for (int i = 0; i < num.size() || carry > 0; ++i) {
        long long product = carry;
        if (i < num.size()) {
            product += (long long)num[i] * x;
        }
        res.push_back(product % 10);
        carry = product / 10;
    }
    // 移除前导零(虽然乘法通常不会产生前导零,但以防万一)
    while (res.size() > 1 && res.back() == 0) {
        res.pop_back();
    }
    return res;
}
// 高精度除法:大整数(用vector存储,低位在前)除以小整数,返回商
long long divide(const vector<int> &num, int y) {
    long long quotient = 0;
    int remainder = 0;
    // 从高位到低位计算
    for (int i = num.size() - 1; i >= 0; --i) {
        long long current = remainder * 10LL + num[i];
        quotient = quotient * 10 + current / y;
        remainder = current % y;
    }
    return quotient;
}
int main() {
    int n;
    cin >> n;
    int king_a, king_b;
    cin >> king_a >> king_b;  // 国王的右手数不影响计算
    
    vector<Minister> ministers(n);
    for (int i = 0; i < n; ++i) {
        cin >> ministers[i].a >> ministers[i].b;
    }
    // 按 a*b 从小到大排序大臣
    sort(ministers.begin(), ministers.end(), compare);
    
    // 用高精度存储乘积(低位在前)
    vector<int> product;
    int temp = king_a;
    if (temp == 0) {
        product.push_back(0);
    } else {
        while (temp > 0) {
            product.push_back(temp % 10);
            temp /= 10;
        }
    }
    long long max_reward = 0;
    for (int i = 0; i < n; ++i) {
        // 当前大臣的奖赏 = 乘积 / 右手数(向下取整)
        long long reward = divide(product, ministers[i].b);
        if (reward > max_reward) {
            max_reward = reward;
        }
        // 更新乘积(乘以当前大臣的左手数)
        product = multiply(product, ministers[i].a);
    }
    cout << max_reward << endl;
    return 0;
}

2025/8/3 16:53
加载中...