- 打卡等级:即来则安
- 打卡总天数:15
- 打卡月天数:1
- 打卡总奖励:117
- 最近打卡:2025-08-02 15:29:27
VIP
- 积分
- 2388
|
一、问题分析这道题目要求我们安排大臣的排列顺序,使得获得最多金币的大臣获得的金币尽可能少。关键在于找到正确的排序规则,并处理大数相乘和相除的问题。 二、解题思路三、关键观察点四、代码实现
- #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;
- }
复制代码
五、代码解析来源:竞赛学习
|
|