按照从枚举到K短路提到的优先队列方法,为保证复杂度的正确,本质上需要把 的 元子集组织成一棵有根树,满足每个点儿子数量为 个,且父亲节点的子集和不小于儿子的。
每个节点如此定义状态:[sum, left, pos, right],表示当前节点代表子集的子集和为 sum,当前子集的最小前 left 个数为 ,而第 left+1 个数位置在 pos,第 left+2 个数位置在 right。它有两个儿子:
- 一个代表将第 left 个数向右移动一个位置,到达状态 [sum-w[pos]+w[pos+1], left, pos+1, right]
- 另一个代表移动完成第 left 个数,转向把第 left-1 个数向右移动一个位置,到达状态 [sum-w[left-1]+w[left], left-1, lef, pos]
并不难实现,实现细节见如下代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll,int,int,int> Node;
int main() {
int n, k, t; scanf("%d%d%d", &n, &k, &t);
vector<int> w(n);
for(auto &g : w) scanf("%d", &g);
sort(w.begin(), w.end(), greater<int>());
priority_queue<Node> pq;
pq.emplace(accumulate(w.begin(), w.begin()+k, 0LL), k-1, k-1, n);
while(!pq.empty() && t) {
auto [sum, lef, pos, rig] = pq.top(); pq.pop();
printf("%lld ", sum), t--;
if(pos < rig-1) pq.emplace(sum-w[pos]+w[pos+1], lef, pos+1, rig);
if(lef && lef < pos) pq.emplace(sum-w[lef-1]+w[lef], lef-1, lef, pos);
}
return 0;
}
注:也可以采用二分答案法,见 AC 提交,但本质和优先队列法是一样的