题解 | #[P1080] 国王游戏(简化版)#

本题看似是一个全排列搜索问题，但 $N=60$ 的规模直接否定了暴力枚举的可能性（ $60!$ 是天文数字）。问题的本质是最小化最大值（Min-Max），这是典型的贪心算法应用场景。我们需要寻找一种局部最优的排序策略，使得其能够直接推导出全局最优解。

算法推导（微扰分析法）

为了确定大臣们的排序规则，我们采用“邻项交换法”（Exchange Argument）进行严格推导。

假设与推导

假设最优序列中，有两位相邻的大臣：大臣 $i$ 排在前面，大臣 $i+1$ 排在后面。设他们之前所有人的左手数字乘积为 $P$ （是一个常数）。大臣 $i$ 的左右手数字为 $(a_i, b_i)$ ，大臣 $i+1$ 的为 $(a_{i+1}, b_{i+1})$ 。

方案 A：顺序为 $(i, i+1)$

大臣 $i$ 获得的金币： $R_1 = \frac{P}{b_i}$
大臣 $i+1$ 获得的金币： $R_2 = \frac{P \times a_i}{b_{i+1}}$
该方案下的局部最大值： $Max_A = \max(\frac{P}{b_i}, \frac{P \times a_i}{b_{i+1}})$

方案 B：交换顺序为 $(i+1, i)$

大臣 $i+1$ 获得的金币： $R'_1 = \frac{P}{b_{i+1}}$
大臣 $i$ 获得的金币： $R'_2 = \frac{P \times a_{i+1}}{b_i}$
该方案下的局部最大值： $Max_B = \max(\frac{P}{b_{i+1}}, \frac{P \times a_{i+1}}{b_i})$

比较分析 我们的目标是让最大值尽可能小。假设方案 A 优于方案 B，即 $Max_A < Max_B$ 。由于 $a_i, b_i \ge 1$ ，容易观察到：

在方案 A 中， $\frac{P \times a_i}{b_{i+1}}$ 显然通常大于 $\frac{P}{b_i}$ （除非 $b$ 极大， $a$ 极小，但即使如此，我们也关注主导项）。
严格推导时，我们可以比较 $Max_A$ 和 $Max_B$ 。去除公因子 $P$ ，我们比较： $\max(\frac{1}{b_i}, \frac{a_i}{b_{i+1}})$ 与 $\max(\frac{1}{b_{i+1}}, \frac{a_{i+1}}{b_i})$
两边同时乘以 $b_i b_{i+1}$ 去分母：比较 $\max(b_{i+1}, a_i b_i)$ 与 $\max(b_i, a_{i+1} b_{i+1})$

由于通常 $a \ge 1$ ，则 $a_i b_i \ge b_i$ 且 $a_{i+1} b_{i+1} \ge b_{i+1}$ 。因此，比较实际上简化为比较各自乘积项的主导地位： $a_i b_i$ 与 $a_{i+1} b_{i+1}$

若我们要使得 $Max_A < Max_B$ ，则需要： $a_i b_i < a_{i+1} b_{i+1}$

结论

为了使获得最多金币的大臣拿到的金币最少，应该将所有大臣按照 左右手数字之积 $(a_i \times b_i)$ 从小到大 进行排序。积越小的排在越前面。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int a0, b0;
    cin >> a0 >> b0;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](int i, int j) {
        return a[i] * b[i] < a[j] * b[j];
    });

    ll prod = a0;
    ll ans = 0;

    for (int i = 0; i < n; i++) {
        int idx = ids[i];
        ans = max(ans, prod / b[idx]);
        prod *= a[idx];
    }

    cout << ans << endl;
}