题目描述：
给你一个整数数组 nums 和一个 正 整数 k 。你可以选择数组的任一 子序列 并且对其全部元素求和。
数组的 第 k 大和 定义为：可以获得的第 k 个 最大 子序列和（子序列和允许出现重复）
返回数组的 第 k 大和 。
子序列是一个可以由其他数组删除某些或不删除元素排生而来的数组，且派生过程不改变剩余元素的顺序。
注意：空子序列的和视作 0 。
数据范围：
$1\le n \le 10^5, -10^9 \le nums[i] \le 10^9$
题解：
子序列限制比较弱，可以随便选，和子集差不多。
如果全是非负数，可以直接排序。考虑找出数组第 $k$ 小的子序列和，然后用子序列和的最大值减去他就能得到答案。
考虑如何得到最小的 $k$ 个子序列的和，可以先直接从小到大排序。
初始为 []，然后考虑加入 [nums[0]]
[nums[0]] 考虑继续加 [nums[0], nums[1]]，或者改为 [nums[1]]
就这样，每次修改当前最后一个元素，改为 $i + 1$ ，或者直接加入 $i + 1$ 。
可以使用 [sum, index]来表示，然后用堆维护，每次取出最小的 [sum, index]，然后加入 [sum - nums[index] + nums[index + 1], index + 1]，[sum + nums[index + 1], index + 1]
如果存在负数，可以把所有的负数变成绝对值。然后用上述方法求出结果。
然后对每一个子序列的结果，加上所有负数的和，可以得到对应的子序列，大小关系是保持不变的。
假设所有非负数和为 $sum1$ ，所有负数和为 $sum2$ 。则所有元素和为 $sum1 - sum2$ 。假设最后得到的第 $k$ 小和为 $sum$ 。
则 $(sum1 - sum2 - sum) + sum2 = sum1 - sum$
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static long long mod = 1e9 + 7;
const long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
long long kSum(vector<int> &nums, int k)
{
long long sumneg = 0;
int n = nums.size();
long long sum = 0;
for (auto &x : nums)
{
if (x < 0)
sumneg += x, x *= -1;
else
sum += x;
}
sort(nums.begin(), nums.end());
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> q;
q.push({0, -1});
int cnt = 1;
while (cnt < k)
{
auto out = q.top();
q.pop();
int curIndex = out.second;
if (curIndex + 1 < n)
q.push({out.first + nums[curIndex + 1], curIndex + 1});
if (curIndex >= 0)
{
if (curIndex + 1 < n)
q.push({out.first - nums[curIndex] + nums[curIndex + 1], curIndex + 1});
}
++cnt;
}
return sum - q.top().first - sumneg;
}
};
|