当前位置：首页 > 提高组 > 洛谷P1080题（2012年NOIP提高组）：国王游戏的高精度计算解法

洛谷P1080题（2012年NOIP提高组）：国王游戏的高精度计算解法

4个月前 (08-06)

一、题目解读

洛谷P1080题要求解决一个关于大臣与国王乘积比较的问题：给定国王和n位大臣的左右能力值，需统计有多少大臣的左右能力乘积小于国王的乘积。题目核心在于处理大数乘积计算与高效比较，需避免整数溢出，因此高精度算法成为关键。

二、解题思路

1. 高精度整数处理：自定义BigInt类，通过vector存储数字逆序各位，支持乘法（逐位相乘+进位处理）与除法（模拟竖式除法），解决大数运算问题。

2. Minister结构设计：定义Minister包含左右能力值，重载<运算符为乘积比较，便于后续排序或筛选。

3. 核心逻辑：遍历大臣，计算其乘积并与国王比较，利用高精度运算确保准确性。

三、解题步骤

1. 输入与初始化：读取国王能力值及大臣数量n，构建Minister数组存储大臣数据。

2. 高精度乘积计算：利用BigInt类的乘法运算，计算每位大臣的左右乘积（若直接使用内置类型可能溢出）。

3. 比较与计数：通过重载的<运算符（乘积比较）判断大臣乘积是否小于国王，累加符合条件的大臣数量。

4. 优化处理：代码中已包含高精度除法（虽未直接用于本题，但为扩展性设计），实际比较仅依赖乘法结果。

四、代码与注释

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

// 高精度整数类
struct BigInt {
    vector<int> digits;
    
    BigInt(int num = 0) {
        while (num) {
            digits.push_back(num % 10);
            num /= 10;
        }
    }
    
    BigInt& operator*=(int num) {
        int carry = 0;
        for (int i = 0; i < digits.size(); ++i) {
            int product = digits[i] * num + carry;
            digits[i] = product % 10;
            carry = product / 10;
        }
        while (carry) {
            digits.push_back(carry % 10);
            carry /= 10;
        }
        return *this;
    }
    
    BigInt operator/(int num) const {
        BigInt res;
        res.digits.resize(digits.size());
        int remainder = 0;
        for (int i = digits.size() - 1; i >= 0; --i) {
            int current = remainder * 10 + digits[i];
            res.digits[i] = current / num;
            remainder = current % num;
        }
        while (res.digits.size() > 1 && res.digits.back() == 0) {
            res.digits.pop_back();
        }
        return res;
    }
    
    bool operator<(const BigInt& other) const {
        if (digits.size() != other.digits.size()) {
            return digits.size() < other.digits.size();
        }
        for (int i = digits.size() - 1; i >= 0; --i) {
            if (digits[i] != other.digits[i]) {
                return digits[i] < other.digits[i];
            }
        }
        return false;
    }
};

struct Minister {
    int left, right;
    bool operator<(const Minister& other) const {
        return left * right < other.left * other.right;
    }
};

int main() {
    int n;
    cin >> n;
    Minister king;
    cin >> king.left >> king.right;
    
    vector<Minister> ministers(n);
    for (int i = 0; i < n; ++i) {
        cin >> ministers[i].left >> ministers[i].right;
    }
    
    // 按左右手乘积排序
    sort(ministers.begin(), ministers.end());
    
    BigInt product(king.left);
    BigInt max_reward(0);
    
    for (int i = 0; i < n; ++i) {
        BigInt reward = product / ministers[i].right;
        if (max_reward < reward) {
            max_reward = reward;
        }
        product *= ministers[i].left;
    }
    
    // 输出最大奖励
    for (int i = max_reward.digits.size() - 1; i >= 0; --i) {
        cout << max_reward.digits[i];
    }
    cout << endl;
    
    return 0;
}