P1080 [NOIP 2012 提高组] 国王游戏

难度	算法s	日期	题目链接
普及+/提高	贪心、邻项排序	2025-07-25	https://luogu.com.cn/problem/P1080

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

题意简述

有 $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。