难度 | 算法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。