本文主要以例题讲解和贪心方法入手。
邻项交换
当我们确定操作顺序，并按照题意模拟即可得出答案，就要用邻项交换的办法来确定最优的操作顺序。
接水问题
对于一个排队顺序 \(T_1\sim T_n\)，答案显然等于：
\[\frac{\sum_{i=1}^{n}{(n-i)\times T_i}}{n} \]那么将其中的 \(T_2,T_3\) 拎出来，将他们交换位置，显然不会影响后面的 \(T\) 的计算，而：
\[(n-1)\times T_2+(n-2)\times T_3 \]变成了：
\[(n-2)\times T_2+(n-1)\times T_3 \]那么如果想让交换前的更优，显然需要满足：
\[(n-1)\times T_2+(n-2)\times T_3 < (n-2)\times T_2+(n-1)\times T_3 \]即：
\[T_2<T_3 \]所以我们要按照 \(T\) 从小到大的顺序进行排序。这样就能取得最优值。
[NOIP2012 提高组] 国王游戏
同样，将排队顺序写出来后，即可按照题意模拟，将答案算出。
直接考虑第 \(i\) 个人的贡献：\(\frac{\prod_{j=1}^{i-1}\;l_j}{r_i}\)，第 \(i+1\) 个人的贡献显然是 \(\frac{\prod_{j=1}^{i}\;l_j}{r_{i+1}}\)，那么交换后，变成 \(\frac{l_{i+1}\; \times \prod_{j=1}^{i-1}\;l_j}{r_i}\) 和 \(\frac{\prod_{j=1}^{i-1}\;l_j}{r_{i+1}}\)，要想交换前更优，显然应该满足：
\[\max\{\frac{\prod_{j=1}^{i-1}\;l_j}{r_i},\frac{\prod_{j=1}^{i}\;l_j}{r_{i+1}}\}<\max\{\frac{l_{i+1}\times \prod_{j=1}^{i-1}\;l_j}{r_i},\frac{\prod_{j=1}^{i-1}\;l_j}{r_{i+1}}\} \]可以转化为比较：
\[\frac{\prod_{j=1}^{i}\;l_j}{r_{i+1}}<\frac{l_{i+1}\times \prod_{j=1}^{i-1}\;l_j}{r_i} \]即：
\[\frac{l_i}{r_{i+1}}<\frac{l_{i+1}}{r_i} \]即：
\[l_i\times r_i<l_{i+1}\times r_{i+1} \]按照这个式子排序即可。
[yLOI2019] 梅深不见冬
先对问题进行简单的分析，如果我们将节点 \(k\) 的子儿子答案全部计算出来（记作 \(ans_i\)，并设权值为 \(v_i\)），并且将进入儿子的顺序确定下来，那么答案就是：
\[\max\{v_k+v_1+v_2+...+v_{siz(son)},ans_1,v_1+ans_2,v_k+v_1+v_2+ans_3...\} \]同样，我们取其中的两个 \(v_k+\sum_{j=1}^{i-1}v_j+ans_i\) 和 \(v_k+\sum_{j=1}^{i}v_j+ans_{i+1}\)，交换后：\(v_k+\sum_{j=1}^{i-1}v_j+ans_{i+1}\) 和 \(v_k+\sum_{j=1}^{i-1}v_j+ans_i+v_{i+1}\)，那么我们只需要比较：
\[v_k+\sum_{j=1}^{i}v_j+ans_{i+1}<v_k+\sum_{j=1}^{i-1}v_j+ans_i+v_{i+1} \]即可，就是满足：
\[v_i-ans_i<v_{i+1}-ans_{i+1} \]处理所有节点时，按照这个排序即可。
标签：frac,sum,交换,笔记,times,ans,prod,贪心 From： https://www.cnblogs.com/zhangyuzhe/p/17666341.html