标签：frac max 邻项 血量 交换法 贪心

贪心

邻项交换法

对于两项 \((a_x,b_x),(a_y,b_y)\)，我们比较谁在前面谁在后面，只需要比较仅有这两项的情况下，谁前谁后是更优的。满足 \(a_i\ge b_i\)。

若 \(x\) 在 \(y\) 前，所需要的血量为 \(\max(a_x,b_x+a_y)\)。

若 \(y\) 在 \(x\) 前，所需要的血量为 \(\max(a_y,b_y+a_x)\)。

我们不妨认为血量是大于 \(\max(a_x,a_y)\) 的。因此我们只需要比较 \(b_x+a_y\) 和 \(b_y+a_x\) 的大小关系，就知道先杀谁会比较好了。

2-其他算法-贪心-邻项交换法

P1080 [NOIP2012 提高组] 国王游戏

对于大臣 \(x,y\)，计算 \(val(x,y)<val(y,x)\) 这个不等式成立的条件。

\[\max(\frac{1}{b_x},\frac{a_x}{b_y}) < \max(\frac{1}{b_y},\frac{a_y}{b_x}) \]

因为我们总是有 \(\frac{1}{b_x}<\frac{a_y}{b_x}\) 和 \(\frac{1}{b_y}<\frac{a_x}{b_y}\)，所以直接按照 \(\frac{a_x}{b_y}<\frac{a_y}{b_x}\) 排序就可以了。建议移项再比较。因为要写高精度，所以我不写了。

标签：frac,max,邻项,血量,交换法,贪心
From： https://www.cnblogs.com/liyixin0514/p/18635910