2386. 找出数组的第 K 大和

第 307 场周赛 Q4 困难2648

给你一个整数数组 nums 和一个正整数 k 。你可以选择数组的任一子序列并且对其全部元素求和。

数组的第 k 大和定义为：可以获得的第 k 个最大子序列和（子序列和允许出现重复）

返回数组的第 k 大和。

子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。

注意：空子序列的和视作 0 。

示例 1：

输入：nums = [2,4,-2], k = 5
输出：2
解释：所有可能获得的子序列和列出如下，按递减顺序排列：
- 6、4、4、2、2、0、0、-2
数组的第 5 大和是 2 。
示例 2：

输入：nums = [1,-2,3,4,-10,12], k = 16
输出：10
解释：数组的第 16 大和是 10 。
py

提示:

$n == nums.length\\ 1 <= n <= 10^5\\ -10^9 <= nums[i] <= 10^9\\ 1 <= k <= min(2000, 2^n)$

题解

我看了提示从可能的最大总和开始，继续寻找下一个最大的总和，直到达到第 k 个总和。后, 发现了: $最大值即\\ 0 + nums中所有正数, \\而k大值 = 最大值 - nums[i](正数) 或者 + nums[i](负数)\\ 即 k大值 = 最大值 - abs(nums[i])$

所以我只需要想办法就可以了, 然后就不会了

正解 By 0x3f

$转换\\$ 计算 $nums$ 中所有非负数的和，记作 $sum$ 。

$nums$ 的任意一个子序列的元素和，都等价于从 $sum$ 中减去某些非负数／加上某些负数得到。

例如 $nums = [1,2,3,-4]$ ，其非负数的和为 $1 + 2 + 3 = 6$ ，我们可以从 $6$ 中减去 $2$ 得到 $nums$ 的子序列 $[1,3]$ 的和 $1 + 3 = 4$ ，也可以把 $6$ 和 $-4$ 相加, 得到 $nums$ 的子序列 $[1,2,3,-4]$ 的和 $2$ 。

注意到，「减去非负数」和「加上负数」都相当于减去 $\left| nums[i] \right |$ 。

$sum$ 减去的数越小， $nums$ 的子序列和就越大。

现在要解决的问题是：

把每个 $nums[i]$ 取绝对值后， $nums$ 的第 $k$ 小的子序列和是多少?
方法二：最小堆

如何不重不漏地生成 $nums$ 的所有子序列?

以有序非负数组 $nums=[1,2,3]$ 为例，有 $2^{3}=8$ 个子序列，生成的方法如下:

从空子序列 [] 开始。
在 [] 末尾添加 1 得到 [1]。
在 [1] 末尾添加 2 得到 [1,2] 。也可以把末尾的 1 替换成 2 得到 [2] 。
在 [2] 末尾添加 3 得到 [2,3] 。也可以把末尾的 2 替换成 3 得到 [3] 。
在 [1,2] 末尾添加 3 得到 [1,2,3] 。也可以把末尾的 2 替换成 3 得到 [1,3] 。

上述过程结合最小堆，就可以按照从小到大的顺序生成所有子序列了（堆中维护子序列的和以及下一个要添加/替换的元素下标）。取生成的第 $k$ 个子序列的和，作为 $sum$ 要减去的数。

问：为什么结合最小堆，就一定是按元素和从小到大的顺序生成的？有没有可能先生成一个大的，再生成一个小的？

答：把子序列和它通过添加/替换生成的子序列之间连一条有向边，我们可以得到一棵以 []为根的有向树。把边权定义成相邻节点的子序列元素和的差，由于 nums 是有序的且没有负数，所以树是没有负数边权的。那么上述算法其实就是在这棵树上跑 Dijkstra 算法。把元素和当作海拔高度，算法执行过程就好比不断上涨的水位，我们会按照海拔高度从低到高淹没节点，所以出堆的元素和是非降的。

class Solution {
public:
    long long kSum(vector<int> &nums, int k) {
        long sum = 0L;
        for (int &x : nums) {
            if (x >= 0) {
                sum += x;
            } else {
                x = -x;
            }
        }
        ranges::sort(nums);

        priority_queue<pair<long, int>, vector<pair<long, int>>, greater<>> pq;
        pq.emplace(0, 0); // 空子序列
        while (--k) {
            auto [s, i] = pq.top();
            pq.pop();
            if (i < nums.size()) {
                // 在子序列的末尾添加 nums[i]
                pq.emplace(s + nums[i], i + 1); // 下一个添加/替换的元素下标为 i+1
                if (i) { // 替换子序列的末尾元素为 nums[i]
                    pq.emplace(s + nums[i] - nums[i - 1], i + 1);
                }
            }
        }
        return sum - pq.top().first;
    }
};

// 作者：灵茶山艾府
// 链接：https://leetcode.cn/problems/find-the-k-sum-of-an-array/solutions/1764389/zhuan-huan-dui-by-endlesscheng-8yiq/
// 来源：力扣（LeetCode）
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
C++

题解

正解 By 0x3f​

正解 By 0x3f