| 难度 | 算法s | 日期 | 题目链接 |
|---|---|---|---|
| 普及+/提高 | 贪心、邻项排序 | 2025-07-25 | https://luogu.com.cn/problem/ |
有 \(n\) 个大臣和一个国王，每个大臣左、右手各有一个数，分别记为 \(a_i,b_i\)，国王手上也有数，记为 \(a,b\)。现在让国王排在队首，大臣按一定顺序排成一列接在国王后面。
每个大臣都会得到国王的金币奖励，对于队伍中排第 \(k\)（\(1\le k\le n\)）的大臣，他得到的金币
也就是他前面所有人（包括国王）左手上的数之积除以他自己右手上的数。现在希望通过恰当地安排大臣的排列顺序，使得 \(\max w_k\)，即获得金币最多的大臣获得的金币数尽可能小。
这是一道经典的邻项排序问题，可以通过这道题学会邻项排序的基本思路。请注意下文中加粗的部分。
思路
对于两个相邻的大臣，分别排在 \(i,j\) 位置上，假设 \(i\lt j\)，他们之前所有人左手上的数的乘积为 \(p\)。那么他们现在得到的金币数分别是：
如果他们交换位置，那么有：
现在我们考虑，如果要满足 \(i\lt j\) 时 \(\max\{w_i,w_j\}\) 比 \(j<i\) 时更小（或相等），即
应该满足什么条件？ 我们考虑分类讨论，然后归纳：
-
首先有以下事实：
\[\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)].\)
所以有：
也就是说，只要相邻的两个大臣 \(i,j\) 满足这个条件，就让 \(i\lt j\)，即大臣 \(i\) 排在前面。
编码
根据这个设计 bool operator<() ，然后用 std::sort() 就可以了。我们可以把国王和大臣的 \(a,b\) 统一存储于一个数组中，但是排序的时候从第二个元素开始排，这样写起来可以简单点。
这题要用高精度才能 AC。