贪心算法学习笔记

咕咕咕... 施工中...

一、贪心的基本思想

贪心，显然是：每一步的决策都基于当前最大利益的选择。

什么是利益？利益就是对最终答案的贡献，是实际的贡献。

我们来看一道题：CF1399E1 Weights Division (easy version) 题解

题意：

给定一棵以 \(1\) 号点为根的带权有根树。

在每次操作中，你可以选择一条边 \(i\)，使得这条边的权值 \(w_i\) 变成 \(\lfloor \frac{w_i}{2} \rfloor\)

找到最小操作数，以满足所有从根到叶子的路径的权值之和不超过 \(S\)。

换句话说，如果设 \(w(i,j)\) 为从节点 \(i\) 到节点 \(j\) 的路径的权值，那么你需要使得 \(\sum_{v \in \mathtt{leaves}} w(\mathtt{root},v) \leq S\)，其中 \(\mathtt{leaves}\) 是所有叶子组成的集合。

不知道你们的想法是什么，反正我的初始想法是按「边权 \(\times\) 经过次数」贪心，不过这个是错误的。

正解是按照 「 \(\left(\texttt{边权}-\left\lfloor\texttt{边权} / 2\right\rfloor\right) \times \texttt{经过次数}\) 」贪心，是不是稍微有点“反直觉”的感觉（

我们的目标是什么？最小化边权和最大的那条链，重点在于“最小化”。

「边权 \(\times\) 经过次数」是什么？它什么都不是，因为它并不是真实提供贡献的，或者说它并不是「利益」

「 \(\left(\texttt{边权}-\left\lfloor\texttt{边权} / 2\right\rfloor\right) \times \texttt{经过次数}\) 」则是实际的利益，这是我们对边消掉的，也就是实际的贡献。

扯了这么多，其实就是想说，要注意什么东西才是最大利益，不要全凭感觉