贪心策略总结

贪心 is so difficult！！！

国王游戏

Problem

题意简介：
有 \(n\) 个大臣，国王左右手上的整数分别是 \(a_0,b_0\)，第 \(i\) 个大臣左右手上的整数分别是 \(a_i,b_i\)。
现在国王和所有大臣将排成一排，国王在队伍最前面，后面的 \(n\) 个大臣的顺序随便排。
排好队后，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
请你安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少，并求出这个最小值。

\(1\le n\le 10^3,0<a_i,b_i<10^4\)

Solution

省流：排序 \(\verb!and!\) 推式子。

设 \(w(x)\) 表示大臣 \(x\) 的奖赏。

假设目前大臣 \(i\) 在大臣 \(j\) 后面，并令大臣 \(i\) 前面所有人左手上的数的积为 \(W\)，可得大臣 \(i\) 和大臣 \(j\) 的奖赏分别为

\[\begin{cases} w(i)=\lfloor\frac{W}{b_i}\rfloor\\ w(j)=\lfloor\frac{W}{a_jb_j}\rfloor \end{cases}\]

往排序上想，考虑大臣 \(i\) 和大臣 \(j\) 在什么情况交换位置后更优。

大臣 \(i\) 和大臣 \(j\) 交换位置后，他们的奖赏分别是

\[\begin{cases} w^\prime(i)=\lfloor\frac{W}{a_jb_i}\rfloor\\ w^\prime(j)=\lfloor\frac{Wa_i}{a_jb_j}\rfloor \end{cases}\]

容易得到，当 \(\max\{w^\prime(i),w^\prime(j)\}<\max\{w(i),w(j)\}\) 时，大臣 \(i\) 和大臣 \(j\) 交换位置后会更优。

再进一步拆分这个东西：

\[\max\{\lfloor\frac{W}{a_jb_i}\rfloor,\lfloor\frac{Wa_i}{a_jb_j}\rfloor\}<\max\{\lfloor\frac{W}{b_i}\rfloor,\lfloor\frac{W}{a_jb_j}\rfloor\} \]

下取整看上去极其之烦，但是直接去掉下取整只会使得这个式子两边取等的次数变少，对答案没有一点影响，所以下取整可以放心大胆地去掉。

式子两边都有 \(W\)，直接除掉它，以简化式子。

\[\max\{\frac{1}{a_jb_i},\frac{a_i}{a_jb_j}\}<\max\{\frac{1}{b_i},\frac{1}{a_jb_j}\} \]

可以发现 \(\dfrac{1}{a_jb_i}<\dfrac{1}{b_i}\verb! and !\dfrac{a_i}{a_jb_j}>\dfrac{1}{a_jb_j}\) 恒成立。

那么可得：

\[\frac{a_i}{a_jb_j}<\frac{1}{b_i} \]

解得 \(a_ib_i<a_jb_j\)。

\(\because\frac{1}{a_jb_i}<\frac{1}{b_i}\le\max\{\frac{1}{b_i},\frac{1}{a_jb_j}\}\)
\(\therefore\) 最后没列出关于 \(\frac{1}{a_jb_i}\) 的不等式。

以此为关键字进行排序，然后 \(\mathcal{O}(n)\) 扫一遍即可。

时间复杂度：\(\mathcal{O}(n\log n)\)
空间复杂度：\(\mathcal{O}(n)\)

均分纸牌

Problem

Johnson 法则

Problem