邻项交换模型
邻项交换十分的重要，因为他是一个不可替代的算法。需要知道什么时候使用邻项交换，没有固定的形态，需要通过做题形成一种经验。
P1080 国王游戏
题目描述
有 \(n\) 个人，每一个人左手写了 \(a_i\) ，右手写了 \(b_i\) 。需要确定一个 \(1,2,\dots,n\) 的排列 \(p\) ,使得最小化：
\[\max_{i=1}^n\{(\prod_{j=1}^{i-1}a_j)\times b_i\} \]思路点拨
通过这个题目体会什么时候可以使用邻项交换。
对于一个顺序中，存在相邻两项 \(j,i\) ,考虑如果将顺序转变为 \(i,j\) 更优需要满足什么条件?
记 \(sum\) 表示 \(j\) 之前项 \(a_i\) 的积,则：
\[\max\{sum\times b_j,sum\times a_j\times b_i\}>\max\{sum\times b_i,sum\times a_i\times b_j\} \]发现存在 \(\max\) 做不了一点，但是考虑 \(sum\times a_j\times b_i>sum\times b_i\) ，所以 \(sum\times b_i\) 没有什么意义，同理，\(sum\times b_j\) 也是一样的。
转化为 \(sum\times a_j\times b_i>sum\times a_i\times b_j,\frac{a_i}{b_i}<\frac{a_j}{b_j}\) 。
所以我们只需要按照 \(\frac{a_i}{b_i}\) 排序就可以了。
接下来说明这个做法为什么是对的：
-
交换的分析是正确的，因为 \(i,j\) 交换不会影响 \(j\) 前面和 \(i\) 后面的元素。并且在分析过程中，发现 \(i,j\) 交换和之前的元素并不相关。
-
最后的排序是对的，因为 \(\frac{a_i}{b_i}<\frac{a_j}{b_j}\) 这种比较是具有传递性的。
这两点也是邻项交换成立的条件。
标签：frac,max,模型,交换,times,sum,邻项,贪心 From： https://www.cnblogs.com/-Aurore-/p/18379320