一个问题

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\)插入堆。
这样子就行了,因为一个状态最多被遍历一次。
(其实这也是追击圣诞老人这道题的技巧)

一个问题

上一篇:Savitzky-Golay 滤波器


下一篇:机器视觉——必备知识