P1080 国王游戏

通过这道题可以了解邻项排序类贪心题目的一般流程。

难度普及+/提高

算法贪心、邻项交换排序

日期2025-07-25

题意简述

有 $n$ 个大臣和一个国王，每个大臣左、右手各有一个数，分别记为 $a_i,b_i$，国王手上也有数，记为 $a,b$。现在让国王排在队首，大臣按一定顺序排成一列接在国王后面。

每个大臣都会得到国王的金币奖励，对于队伍中排第 $k$（$1\le k\le n$）的大臣，他得到的金币

$$w_k=\cfrac{a\prod_{i=1}^ka_k}{b_k}.$$

也就是他前面所有人（包括国王）左手上的数之积除以他自己右手上的数。现在希望通过恰当地安排大臣的排列顺序，使得 $\max w_k$，即获得金币最多的大臣获得的金币数尽可能小。

这是一道经典的邻项排序问题，可以通过这道题学会邻项排序的基本思路。请注意下文中加粗的部分。

思路

对于两个相邻的大臣，分别排在 $i,j$ 位置上，假设 $i\lt j$，他们之前所有人左手上的数的乘积为 $p$。那么他们现在得到的金币数分别是：

$$w_i=\frac{p}{b_i},w_j=\frac{p\times a_i}{b_j},$$

如果他们交换位置，那么有：

$$w_i^\prime=\frac{p\times a_j}{b_i},w_j^\prime=\frac{p}{b_j}.$$

现在我们考虑，如果要满足 $i\lt j$ 时 $\max\{w_i,w_j\}$ 比 $j<i$ 时更小（或相等），即

$$\max\{\frac{p}{b_i},\frac{p\times a_i}{b_j}\}\le\max\{\frac{p\times a_j}{b_i},\frac{p}{b_j}\},$$

应该满足什么条件？ 我们考虑分类讨论，然后归纳：

• 首先有以下事实：

  $$\frac{p}{b_i}\le \frac{p\times a_j}{b_i},\frac{p\times a_i}{b_j}\ge\frac{p}{b_j}.$$

• 由上述事实可知，当左侧 $p/b_i$ 成为最大值时，右侧一定 $\ge$ 左侧（因为右侧 $\ge(p\times a_j)/b_i$）。为了让左侧 $p/b_i$ 成为最大值，需要满足：

  $$\frac{p}{b_i}\ge\frac{p\times a_i}{b_j}\Rightarrow b_j\ge a_i\times b_i.(1)$$

• 对于另一种情况，左侧 $(p\times a_i)/b_j$ 成为最大值时，考虑右侧情况：

  • 如果 $p/b_j$ 是最大值，那么由事实可知右侧一定小于左侧了，情况不成立。

  • 所以一定是 $(p\times a_j)/b_i$ 成为最大值。

  为了让右侧 $(p\times a_j)/b_i$ 成为最大值，需要满足：

  $$\frac{p\times a_j}{b_i}\ge\frac{p}{b_j}\Rightarrow a_j\times b_j\ge b_i.(2)$$

  但是这似乎没什么用，再想想能找到什么条件。我们还要让此时右侧最大值 $\ge$ 左侧最大值，即：

  $$\frac{p\times a_j}{b_i}\ge\frac{p\times a_i}{b_j}\Rightarrow a_j\times b_j \ge a_i \times b_i.(3)$$

我们得到了三个不等式，现在进行归纳。我们想要的终极约束不等式$(*)=(1)\cup[(2)\cap(3)].$

所以有：

$$a_j\times b_j\ge a_i\times b_i.(*)$$

也就是说，只要相邻的两个大臣 $i,j$ 满足这个条件，就让 $i\lt j$，即大臣 $i$ 排在前面。

编码

根据这个设计 bool operator<() ，然后用 std::sort() 就可以了。我们可以把国王和大臣的 $a,b$ 统一存储于一个数组中，但是排序的时候从第二个元素开始排，这样写起来可以简单点。

这题要用高精度才能 AC，否则只有 $80pts$。

$80pts$ 代码，可以作思路参考 · 用时 41 ms 内存 628.00 KB

/*
* P1080 [NOIP 2012 提高组] 国王游戏
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1000;
struct Minister {
    ull a, b;
    bool operator<(const Minister& another) {
        return a * b < another.a * another.b;
    }
} mn[MAXN + 1];
int main() {
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        cin >> mn[i].a >> mn[i].b;
    }
    sort(mn + 1, mn + n + 1);
    ull ans = 0, p = mn[0].a;
    for (int i = 1; i <= n;i++) {
        ans = max(ans, p / mn[i].b);
        p *= mn[i].a;
    }
    cout << ans;
    return 0;
}

用时 2.92 s 内存 2.10 MB

/*
* P1080 [NOIP 2012 提高组] 国王游戏
* __uint128_t 拼尽全力无法战胜
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int MAXN = 1e4;
unsigned Log2[10000 + 1];
class BigNumber {
    static const unsigned MAX = 1e5;
    static const unsigned BASE = 1e4;
    unsigned num[MAX + 1];
    int len = 0;
    void solveLen(int max) {
        for (int i = max - 1; i >= 0; i--) {
            if (num[i]) {
                len = i + 1;
                return;
            }
        }
    }
public:
    BigNumber(ull x) {
        memset(num, 0, (MAX + 1) * sizeof(unsigned));
        while (x) {
            num[len] = x % BASE, x /= BASE;
            len++;
        }
    }
    void write() const {
        for (int i = len - 1; i >= 0; i--) {
            if (i < len - 1) {
                if (num[i] < 10) printf("000");
                else if (num[i] < 100) printf("00");
                else if (num[i] < 1000) printf("0");
            }
            printf("%d", num[i]);
        }
        if (len == 0) putchar('0');
    }
    // 数运算
    BigNumber operator*(const unsigned another) const {
        BigNumber res(0);
        int lenAnother = ceil(Log2[another] / Log2[BASE]) + 1;
        for (int i = 0; i < len; i++) {
            res.num[i] = num[i] * another;
        }
        for (int i = 0; i < len + lenAnother - 1; i++) {
            res.num[i + 1] += res.num[i] / BASE;
            res.num[i] %= BASE;
        }
        res.solveLen(len + lenAnother);
        return res;
    }
    friend BigNumber operator*(unsigned a, BigNumber b) {
        return b * a;
    }
    BigNumber operator/(const unsigned another) const {
        BigNumber res(0);
        unsigned tmp[MAX + 1];
        memset(tmp, 0, (MAX + 1) * sizeof(unsigned));
        unsigned tcnt = 0, remainder = 0;
        bool start = false;
        for (int i = len - 1; i >= 0; i--) {
            if ((num[i] + remainder) / another) {
                start = true;
                tmp[tcnt] = (num[i] + remainder) / another;
            }
            remainder = (num[i] + remainder) % another;
            remainder *= BASE;
            if (start) tcnt++;
        }
        for (int i = 0; i < tcnt; i++) {
            res.num[tcnt - i - 1] = tmp[i];
        }
        res.len = tcnt;
        return res;
    }
    // 比较
    bool operator<(const BigNumber& another) const {
        if (len != another.len) return len < another.len;
        for (int i = len - 1; i >= 0; i--) {
            if (num[i] < another.num[i]) return true;
            else if (num[i] > another.num[i]) return false;
        }
        return false;
    }
};
// 大臣
struct Minister {
    unsigned a, b;
    bool operator<(const Minister& another) {
        return a * b < another.a * another.b;
    }
} mn[MAXN + 1];
unsigned read() {
    char ch = getchar();
    while (not isdigit(ch)) ch = getchar();
    unsigned res = 0;
    while (isdigit(ch)) {
        res = (res << 1) + (res << 3) + (ch ^ 48);
        ch = getchar();
    }
    return res;
}
char str[50];
int scnt = 1;
int main() {
    for (int i = 1; i <= 10000; i++) {
        Log2[i] = Log2[i >> 1] + 1;
    }
    int n = read();
    for (int i = 0; i <= n; i++) {
        mn[i].a = read(), mn[i].b = read();
    }
    sort(mn + 1, mn + n + 1);
    BigNumber ans = 0, p = mn[0].a;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, p / mn[i].b);
        p = p * mn[i].a;
    }
    ans.write();
    return 0;
}