题目解析

本题要求对于每个 $k$，计算能够保证 Bajtazar 按照给定顺序至少选择 $k$ 个物品的最小背包承重。

核心思路

代码采用了一种逆向处理的贪心策略：

1. 初始状态：背包承重为所有物品重量之和时，可以选中所有物品
2. 逆向推导：从能选 $n$ 个物品开始，逐步减少到选 $1$ 个物品，计算每个阶段的最小承重
3. 关键观察：为了减少选中的物品数量，需要移除某些物品，但移除一个物品可能会影响后续物品的选择

算法步骤

1. 预处理

• 计算后缀和数组 $s[i]$，表示从第 $i$ 个物品到最后一个物品的重量和
• 构建线段树，每个叶子节点存储 $w[i] - s[i+1]$，这个值表示选择第 $i$ 个物品时的"剩余容量影响"

2. 逆向处理

对于从 $n-1$ 到 $1$ 的每个 $k$：

1. 寻找可移除物品：

   • 使用线段树找到所有 $w[i] - s[i+1] > 0$ 的物品
   • 这些物品在移除后不会影响后续物品的选择

2. 贪心选择：

   • 从可移除物品中选择重量最大的进行移除
   • 保持当前选中物品数量为 $k$

3. 更新状态：

   • 更新总重量：减去被移除物品的重量
   • 更新线段树：调整相关区间的值

3. 输出结果

• 将逆向计算的结果正序输出
• 最后一个值对应 $k = n$ 的情况，即所有物品重量之和

复杂度分析

• 时间复杂度：$O(n \log n)$
  • 构建线段树：$O(n)$
  • 每次查询和更新：$O(\log n)$
  • 总共进行 $n-1$ 次操作
• 空间复杂度：$O(n)$

算法正确性

该算法的正确性基于以下观察：

1. 当背包承重足够大时，所有物品都会被选中
2. 减少承重时，需要移除某些物品
3. 优先移除重量大且移除后不影响后续选择的物品是最优策略
4. 线段树高效维护了移除物品对后续选择的影响

算法标签

• 贪心算法
• 线段树
• 反悔贪心

样例验证

对于样例输入：

6
10 8 3 30 5 10

输出：

3 13 21 26 36 66

验证第二个数 $13$：

• 承重为 $13$ 时，选择过程：
  • 选物品1（重量10，剩余3）
  • 跳过物品2（重量8 > 3）
  • 选物品3（重量3，剩余0）
  • 总共选中2个物品，符合要求

这种方法通过逆向处理和高效的数据结构，解决了大规模数据下的最优解计算问题。