AT_abc376_g [ABC376G] Treasure Hunting 题解 / 邻项合并法学习笔记

zrl123456 · 2025-11-05 21:13:59 · 题解

:::::info[题目基本信息] 考察：贪心（2858）。
题目简介：

• \forall i\in[1,n],a_i\ge 1
• \sum_{i=1}^na_i\le 10^8

  ::::: 注意到这个题我们不能直接贪心选更优的点，因为更劣的点下可能有特别优的点，但是我们注意到这时选完这个劣点下一步肯定会直接选这个优点，这时我们就可以直接合并这两个点。
  现在我们要对“优”进行定义。
  我们一开始每个点的权值不妨直接设为 a_i，最后的时候再除以一个 \displaystyle\sum_{i=1}^na_i 即可，那么合并后的点的权值是什么呢？
  这时，这个大点会对操作次数贡献 2，那么我们不妨考虑邻项交换法，令 x 点的实际点数为 b_x，实际点的编号构成序列 \{id_{x,b_x}\}，对 y 点做相同的定义。
  这时我们要求 x 点在前，那么我们得到：

  (\sum_{i=1}^{b_x}ia_{id_{x,i}})+(\sum_{i=1}^{b_y}(i+b_x)a_{id_{y,i}})<(\sum_{i=1}^{b_y}ia_{id_{y,i}})+(\sum_{i=1}^{b_x}(i+b_y)a_{id_{x,i}})

  解得：\dfrac{\sum_{i=1}^{b_x}a_{id_{x,i}}}{b_x}>\dfrac{\sum_{i=1}^{b_y}a_{id_{y,i}}}{b_y}。
  这样我们就容易得到任意点的权值了。
  后面就可以直接用堆和并查集维护了，细节还是见代码。
  code