分组选择

每组至多选一个带权元素,按权值降序加入;是贪心选择模型的最小入门题,也是划分拟阵的实例。

标签 贪心 / 选择 / 分组 / 拟阵

题目描述

有 𝑚 个组和 𝑛 个元素。第 𝑖 个元素属于第 𝑔𝑖 组,权值为 𝑤𝑖>0。

选择一个元素集合 𝑆,使每个组中至多有一个元素被选中,并最大化

∑𝑖∈𝑆𝑤𝑖.

1≤𝑛≤2×105,1≤𝑚≤𝑛,1≤𝑤𝑖≤109。

题解

本题对应贪心选择模型:

  • 𝐸={1,…,𝑛}:所有元素;
  • ℱ︀:每个组至多选一个元素的集合族;
  • 𝑐(𝑒)=−𝑤𝑒,故 𝐶(𝑆)=−∑𝑒∈𝑆𝑤𝑒;
  • 𝑐 的非减序就是 𝑤 的非增序;
  • 极大可行集:每个非空组各选一个元素;
  • 最优解:使 𝐶(𝑆) 最小,即权和最大。

把所有元素按权值从大到小排序。维护每个组是否已经选过元素。

依次扫描元素 𝑖:

  • 若第 𝑔𝑖 组已经选过元素,跳过;
  • 否则选中 𝑖,并把第 𝑔𝑖 组标记为已选。

正确性用交换论证。设当前贪心集合为 𝑆,并假设存在最优解 𝑂 满足 𝑆⊆𝑂。处理元素 𝑖 时:

  • 若 𝑔𝑖 已被 𝑆 使用,则 𝑂 中也有同组元素,不能再选 𝑖,跳过安全。
  • 若 𝑔𝑖 未被 𝑆 使用:

    • 若 𝑖∈𝑂,不变量保持;
    • 若 𝑖∉𝑂,且 𝑂 中有同组元素 𝑗,则用 𝑖 替换 𝑗。由于按权值降序处理,𝑤𝑖≥𝑤𝑗,替换后仍可行且总权值不降;
    • 若 𝑂 中没有同组元素,则加入 𝑖 不破坏可行性且总权值增大,矛盾。

因此每一步都保持“存在最优解包含当前贪心集合”,最终贪心集合就是最优解。

该可行集族就是划分拟阵的独立集族,因此这也为拟阵页提供了一个直接实例。

复杂度

排序为 𝑂(𝑛log𝑛),扫描为 𝑂(𝑛),空间为 𝑂(𝑛+𝑚)。

参考

源码位置