找回密码
 立即注册
查看: 24|回复: 0

(NOIP2012提高组)洛谷P1080题解:用贪心策略解决国**游戏

[复制链接]
  • 打卡等级:即来则安
  • 打卡总天数:15
  • 打卡月天数:1
  • 打卡总奖励:117
  • 最近打卡:2025-08-02 15:29:27

21

主题

5

回帖

2388

积分

VIP

积分
2388
发表于 2025-7-31 10:25:19 | 显示全部楼层 |阅读模式
截图未命名.jpg
一、问题分析

这道题目要求我们安排大臣的排列顺序,使得获得最多金币的大臣获得的金币尽可能少。关键在于找到正确的排序规则,并处理大数相乘和相除的问题。

二、解题思路
  • ‌排序规则确定‌:通过数学推导得出,应该按照左右手数字乘积从小到大排序
  • 高精度处理‌:由于数字可能很大,需要使用高精度计算
  • ‌**值计算‌:遍历排序后的大臣序列,计算每个大臣获得的金币数并找出**值

三、关键观察点
  • 排序规则:a.left * a.right < a[j].left * a[j].right
  • 国**始终在最前面
  • 需要处理大数相乘和相除的问题

四、代码实现
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;

  5. // 高精度整数类
  6. struct BigInt {
  7.     vector<int> digits;
  8.    
  9.     BigInt(int num = 0) {
  10.         while (num) {
  11.             digits.push_back(num % 10);
  12.             num /= 10;
  13.         }
  14.     }
  15.    
  16.     BigInt& operator*=(int num) {
  17.         int carry = 0;
  18.         for (int i = 0; i < digits.size(); ++i) {
  19.             int product = digits[i] * num + carry;
  20.             digits[i] = product % 10;
  21.             carry = product / 10;
  22.         }
  23.         while (carry) {
  24.             digits.push_back(carry % 10);
  25.             carry /= 10;
  26.         }
  27.         return *this;
  28.     }
  29.    
  30.     BigInt operator/(int num) const {
  31.         BigInt res;
  32.         res.digits.resize(digits.size());
  33.         int remainder = 0;
  34.         for (int i = digits.size() - 1; i >= 0; --i) {
  35.             int current = remainder * 10 + digits[i];
  36.             res.digits[i] = current / num;
  37.             remainder = current % num;
  38.         }
  39.         while (res.digits.size() > 1 && res.digits.back() == 0) {
  40.             res.digits.pop_back();
  41.         }
  42.         return res;
  43.     }
  44.    
  45.     bool operator<(const BigInt& other) const {
  46.         if (digits.size() != other.digits.size()) {
  47.             return digits.size() < other.digits.size();
  48.         }
  49.         for (int i = digits.size() - 1; i >= 0; --i) {
  50.             if (digits[i] != other.digits[i]) {
  51.                 return digits[i] < other.digits[i];
  52.             }
  53.         }
  54.         return false;
  55.     }
  56. };

  57. struct Minister {
  58.     int left, right;
  59.     bool operator<(const Minister& other) const {
  60.         return left * right < other.left * other.right;
  61.     }
  62. };

  63. int main() {
  64.     int n;
  65.     cin >> n;
  66.     Minister king;
  67.     cin >> king.left >> king.right;
  68.    
  69.     vector<Minister> ministers(n);
  70.     for (int i = 0; i < n; ++i) {
  71.         cin >> ministers[i].left >> ministers[i].right;
  72.     }
  73.    
  74.     // 按左右手乘积排序
  75.     sort(ministers.begin(), ministers.end());
  76.    
  77.     BigInt product(king.left);
  78.     BigInt max_reward(0);
  79.    
  80.     for (int i = 0; i < n; ++i) {
  81.         BigInt reward = product / ministers[i].right;
  82.         if (max_reward < reward) {
  83.             max_reward = reward;
  84.         }
  85.         product *= ministers[i].left;
  86.     }
  87.    
  88.     // 输出**奖励
  89.     for (int i = max_reward.digits.size() - 1; i >= 0; --i) {
  90.         cout << max_reward.digits[i];
  91.     }
  92.     cout << endl;
  93.    
  94.     return 0;
  95. }
复制代码






五、代码解析
  • ‌BigInt类‌:实现高精度整数的存储和基本运算
  • ‌Minister结构体‌:存储大臣的左右手数字,并实现排序规则
  • ‌主程序‌:读取输入、排序大臣、计算**金币数

来源:竞赛学习





您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

SEO网站 ( 冀ICP备2025113422号-2 )|网站地图

Powered by Discuz! X3.5

快速回复 返回顶部 返回列表