一个问题

https://csacademy.com/contest/round-79/task/smallest-subsets/
给定一个元素全为正整数的序列(a),定义一个长度(k)的子序列(i)的权值为(sum_{j=1}^ka_{i_j})
询问权值排名第(l)小的子序列的权值。
做法:先考虑空序列,把它插入堆内。
每次弹出堆内最小的序列。
如果在中间插入,则一个集合会被插入多次。
考虑在末尾插入,即考虑所有(i)的最大值(p),把这个序列和(p)连接起来的结果插入堆。
这样子显然太慢。
(a)从小到大排序。
设集合中最大值(mx),把(mx+1)添加进序列的末尾插入堆。
或者去掉(mx),再把(mx+1)插入堆。
这样子就行了,因为一个状态最多被遍历一次。
(其实这也是追击圣诞老人这道题的技巧)

原文地址:https://www.cnblogs.com/ctmlpfs/p/14967408.html