- 国王游戏
WA
- 2025-7-6 13:50:28 @
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
struct Minister {
int left, right;
};
bool compare(const Minister &a, const Minister &b) {
return a.left * a.right < b.left * b.right;
}
string multiply(string num1, int num2) {
string res;
int carry = 0;
for (int i = num1.size() - 1; i >= 0; --i) {
int product = (num1[i] - '0') * num2 + carry;
res.push_back(product % 10 + '0');
carry = product / 10;
}
while (carry) {
res.push_back(carry % 10 + '0');
carry /= 10;
}
reverse(res.begin(), res.end());
return res;
}
string divide(string num, int divisor) {
string res;
int idx = 0;
int temp = num[idx] - '0';
while (temp < divisor && idx + 1 < num.size()) {
temp = temp * 10 + (num[++idx] - '0');
}
while (idx < num.size()) {
res += (temp / divisor) + '0';
temp = (temp % divisor) * 10 + (++idx < num.size() ? num[idx] - '0' : 0);
}
return res.empty() ? "0" : res;
}
bool greaterThan(const string &a, const string &b) {
if (a.size() != b.size()) return a.size() > b.size();
return a > b;
}
int main() {
int n;
cin >> n;
int kingLeft, kingRight;
cin >> kingLeft >> kingRight;
vector<Minister> ministers(n);
for (int i = 0; i < n; ++i) {
cin >> ministers[i].left >> ministers[i].right;
}
sort(ministers.begin(), ministers.end(), compare);
string maxReward = "0";
string product = to_string(kingLeft);
for (int i = 0; i < n; ++i) {
string reward = divide(product, ministers[i].right);
if (greaterThan(reward, maxReward)) {
maxReward = reward;
}
product = multiply(product, ministers[i].left);
}
cout << maxReward << endl;
return 0;
}
0 条评论
目前还没有评论...
信息
- ID
- 465
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 13
- 已通过
- 3
- 上传者