2012S_2：国王游戏

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-10-14 15:32:36
 * 最后修改: 2025-10-14 16:24:13
 * 文件描述:国王游戏  不用高精度乘法
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Node { ll a, b; };
// 比较 a1*b1 与 a2*b2（尽量不用高精）
bool cmp(const Node& X, const Node& Y){
        if (X.a * X.b != Y.a * Y.b) return X.a * X.b < Y.a * Y.b;
        return X.a < Y.a;// 次关键字（可选）：按 a 升序
}

int main(){
    int n;
    ll kingA, kingB;
    cin>>n;
    cin >> kingA >> kingB;
    vector<Node> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i].a >> v[i].b;
    sort(v.begin(), v.end(), cmp);
    ll P = kingA; // 前缀乘积从国王左手开始
    ll ans = 0;
    for (int i = 0; i < n; ++i) {
    ll cur = P /v[i].b;;  // 计算当前人的赏金
       if (cur > ans) ans = cur;
       P *= v[i].a; // 前缀乘积乘上 a_i
    }
    cout << ans << "\n";
    return 0;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

int N;  // 大臣人数
pair<int, int> king;  // 国王的左右手数
vector<pair<int, int>> ministers;  // 存储每个大臣的左右手数
int ans[20000], t[20000], lena, lent, tt[20000], t2[20000], len;  // 高精度计算用的数组

// 比较函数，用于排序大臣的乘积
bool compareMinisters(const pair<int, int>& a, const pair<int, int>& b) {
    return a.first * a.second < b.first * b.second;
}

// 初始化函数，读取输入
void initialize() {
    cin >> N >> king.first >> king.second;  // 读取国王的左右手数
    ministers.resize(N);  // 调整大臣数据的大小
    for (int i = 0; i < N; i++) {
        cin >> ministers[i].first >> ministers[i].second;  // 每个大臣的左右手数
    }
}

// 计算当前大臣的奖赏
void calculateReward(int leftProduct, int currentRight) {
    for (int i = 1; i <= lent; i++) {
        tt[i] += t[i] * leftProduct;  // 更新乘积
        tt[i + 1] += tt[i] / 10;  // 处理进位
        tt[i] %= 10;
    }
    lent++;
    while (tt[lent] >= 10) {
        tt[lent + 1] = tt[lent] / 10;
        tt[lent] %= 10;
        lent++;
    }
    while (lent > 1 && tt[lent] == 0) lent--;  // 去除前导零
    len = lent;
    memcpy(t, tt, sizeof(tt));  // 复制结果

    memset(tt, 0, sizeof(tt));
    for (int i = 1, j = len; i <= len; i++, j--)
        t2[i] = t[j];  // 逆序

    int carry = 0, remainder = 0;
    for (int i = 1; i <= len; i++) {
        remainder = carry * 10 + t2[i];
        tt[i] = remainder / currentRight;
        carry = remainder % currentRight;
    }

    int startIndex = 1;
    while (startIndex < len && tt[startIndex] == 0) startIndex++;

    memset(t2, 0, sizeof(t2));
    for (int i = 1, j = startIndex; j <= len; i++, j++)
        t2[i] = tt[j];
    memcpy(tt, t2, sizeof(t2));
    len = len + 1 - startIndex;
}

// 比较当前计算结果是否更优
bool isBetter() {
    if (len > lena) return true;
    if (len < lena) return false;
    for (int i = 1; i <= len; i++) {
        if (ans[i] < tt[i]) return true;
        if (ans[i] > tt[i]) return false;
    }
    return false;
}

// 核心求解函数
void solve() {
    // 使用 std::sort 对大臣按乘积排序
    sort(ministers.begin(), ministers.end(), compareMinisters);

    t[1] = 1; lent = 1;  // 初始化乘积为1

    for (int i = 0; i < N; i++) {
        memset(tt, 0, sizeof(tt));  // 清空临时数组
        len = 0;

        int leftProduct = (i == 0) ? king.first : ministers[i - 1].first;
        int currentRight = ministers[i].second;
        calculateReward(leftProduct, currentRight);  // 计算当前大臣的奖赏

        if (isBetter()) {  // 如果当前结果更优，则更新
            memcpy(ans, tt, sizeof(tt));
            lena = len;
        }
    }

    // 输出最终答案
    for (int i = 1; i <= lena; i++) {
        cout << ans[i];
    }
    cout << endl;
}

int main() {
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    initialize();  // 读取输入
    solve();  // 求解并输出结果
    return 0;
}