$[Acwing\ 114]$ 国王游戏

题目大意

给出$n$个元素，每个元素有两个属性$a_i,b_i$，且满足$\forall 1\le i\le n,0< a_i,b_i$求出一种排列使得
$$ \max\limits_{1\le k\le n}(\frac{1}{b_k}\prod_{i=1}^{k-1}a_i) $$
最小

分析

记$f_k=\frac{1}{b_k}\prod_{i=1}^{k-1}a_i$

对于任一种排列，考虑交换第$i$个元素和第$i+1$个元素，对于任意$1\le k\le n,k\not=i,k\not=i+1$。其$f_k$都不会变化。

交换前的$f_i,f_{i+1}$
$$ f_i=\frac{1}{b_i}\prod_{k=1}^{i-1}a_k,f_{i+1}=\frac{1}{b_{i+1}}\prod_{k=1}^{i}a_k $$
交换后的$f_i’,f_{i+1}’$
$$ f_i’=\frac{1}{b_{i+1}}\prod_{k=1}^{i-1}a_k,f_{i+1}’=\frac{a_{i+1}}{b_i}\prod_{k=1}^{i-1}a_k $$
因此我们要比较的即
$$ \max(f_i,f_{i+1}),\max(f_i’,f_{i+1}’) $$
$$ f_{i+1}=\frac{a_i}{b_i+1}\prod_{k=1}^{i-1}a_k $$
因此我们要比较的即
$$ \max(\frac{1}{b_i},\frac{a_i}{b_{i+1}}),\max(\frac{1}{b_{i+1}},\frac{a_{i+1}}{b_i}) $$
每个分式上下乘上$b_ib_{i+1}$，要比较的即
$$ \max(b_{i+1},a_ib_i),\max(b_i,a_{i+1}b_{i+1}) $$

$$ \forall 1\le i\le n,0< a_i,b_i\Rightarrow \begin{cases}a_ib_i\ge b_i \\\a_ib_i\ge a_i \\\ b_{i+1}\le a_{i+1}b_{i+1}\\\ a_{i+1}\le a_{i+1}b_{i+1} \end{cases} $$

分析两种情况：

情况一：

$\max(b_{i+1},a_ib_i)\le\max(b_i,a_{i+1}b_{i+1})$时（即交换前最优时）

$\max(b_{i+1},a_ib_i)=b_{i+1}$时

$$ \begin{cases}b_{i+1}\ge b_{i+1}\ge a_ib_i \\\a_ib_i\ge b_i \end{cases}\Rightarrow b_{i+1}\ge b_i $$

$$ \begin{cases}b_{i+1}\ge b_i \\\a_{i+1}b_{i+1}\ge b_{i+1} \end{cases}\Rightarrow a_{i+1}b_{i+1}\ge b_i $$

即$\max(b_i,a_{i+1}b_{i+1})=a_{i+1}b_{i+1}$

且满足于$a_ib_i\le b_{i+1}\le a_{i+1}b_{i+1}$

$\max(b_{i+1},a_ib_i)=a_ib_i$时：

$a_ib_i\ge b_i$ ，且$a_ib_i\le a_{i+1}b_{i+1}$

情况二：

$\max(b_{i+1},a_ib_i)\ge\max(b_i,a_{i+1}b_{i+1})$时（即交换后最优时）

$\max(b_i,a_ib_i)=a_ib_i$时，
在满足$a_ib_i\ge a_{i+1}b_{i+1}$时成立

且满足$a_ib_i\ge a_{i+1}b_{i+1}$时，一定满足$\max(b_i,a_ib_i)=a_ib_i$

即如果存在一个逆序对，那么减少这个逆序对结果不会变坏而增加逆序对结果则一定不会更优。

而任一一个序列都能通过邻项交换变成有序序列使得逆序对个数为$0$，因此将$a_ib_i$从小到大排列即可得到最优解。

$[AcWing 734]$ 能量石

题面

岩石怪物杜达生活在魔法森林中，他在午餐时收集了$N$块能量石准备开吃。

由于他的嘴很小，所以一次只能吃一块能量石。

能量石很硬，吃完需要花不少时间。

吃完第 $i$ 块能量石需要花费的时间为$S_i$秒。

杜达靠吃能量石来获取能量。

不同的能量石包含的能量可能不同。

此外，能量石会随着时间流逝逐渐失去能量。

第 $i$ 块能量石最初包含Ei单位的能量，并且每秒将失去$L_i$单位的能量。

当杜达开始吃一块能量石时，他就会立即获得该能量石所含的全部能量（无论实际吃完该石头需要多少时间）。

能量石中包含的能量最多降低至$0$。

请问杜达通过吃能量石可以获得的最大能量是多少？

分析

观察发现，其选择的能量石有可能仅为部分能量石，而确定了组合之后我们要确定其排列，因为同几种能量石其排列的不同有可能影响其收益。

假定当前所选的能量石为$k$个，考虑怎样的排列是最优的。

对于任一排列$a_1,a_2,a_3,…a_k$

考虑任两项$a_i,a_{i+1}$

其交换后，不影响其他能量石的收益。

假定收集完第$i-1$块能量石时是第$k$秒，考虑交换前和交换后的收益：

交换前：
$$ E_i-kL_i+E_{i+1}-(k+S_i)L_{i+1}=E_i+E_{i+1}-(kL_i+(k+S_i)L_{i+1}) $$
交换后：
$$ E_{i+1}-kL_{i+1}+E_i-(k+S_{i+1})Li=E_i+E_{i+1}-(kL_{i+1}+(k+S_{i+1}L_i)) $$
因此，我们只需要比较
$$ kL_i+(k+S_i)L_{i+1},kL_{i+1}+(k+S_{i+1}L_i) $$
的大小
且
$$ kL_i+(k+S_i)L_{i+1}=k(L_i+L_{i+1})+S_iL_{i+1} $$
$$ kL_{i+1}+(k+S_{i+1}L_i)=k(L_i+L_{i+1})+S_{i+1}Li $$
因此要比较的即
$$ S_iL_{i+1},S_{i+1}L_{i} $$
交换前更优，即
$$ S_iL_{i+1}\le S_{i+1}L_{i} $$
交换后更优，即：
$$ S_iL_{i+1}\ge S_{i+1}L_{i} $$
因此直接按$S_iL_{i+1},S_{i+1}L_{i}$排序即可。

因此，对于任一种组合我们是能唯一确定一种最大的排列的。

因此，直接在排序后做$01$背包即可