NOIP2024集训Day65 贪心

NOIP2024集训Day65 贪心

A. [NOI2015] 荷马史诗

简化题意，即构造一颗 \(k\) 叉树，每个节点的权值为其所有孩子的权值之和，给定的 \(n\) 个数必须使用，其余空缺处用 \(0\) 补全。

考虑使用优先队列，首先弹入 \(n + (n-1) \% (k-1)\) 个元素（不足处用 0 代替），然后每次弹出前 \(k\) 小的数并插入其和，直到优先队列中只剩余一个元素。计算时同时保存深度。

由于优先队列默认从大到小排序, 而用 pair 比较方便, 所以处理时我们将队列中的数取反，计算结果时再次取相反数。

B. [CCO2020] Exercise Deadlines

题目可以转化成：构造一个排列，满足 \(p_i≤d_i\)，要求 \(p\) 逆序对个数尽可能少。

直接贪心，从后往前贪心取没有被取的数且 \(\le d_i\) 中最大的。容易证明取更小的会使逆序对个数增加，并且更不容易合法。

最后再求一遍逆序对个数，复杂度 \(\Theta(n\log n)\)。

D. [HNOI2015] 菜肴制作

如果用一个小根堆来维护拓扑的话显然是不行的，因为这样求出来的是字典序最小的拓扑序，并不一定是 \(1\) 尽可能在前，因为字典序是贪心的，如果前面的一位能小就尽可能的小，并不保证 \(1\) 出现尽量靠前。

但是如果建一个反图，求一个反向字典序最大的拓扑序，那就会有大的数尽量靠前的情况出现，于是较小的数尽量靠后，于是反过来就是较小的数尽量靠前了。

所以反着建图，用大根堆维护，然后反向输出就好了。