子序列&&子串

作者： 作者的头像   橙外 ,  2024-03-09 10:48:47 ,  所有人可见 ,  阅读 49

2


子序列:可以不连续 || 子串:必须连续

$Query.1$求一个序列(元素非负)第$k$小(大)的子序列和

先对序列从小到大排序,然后先将第一个元素放入小根堆中

当遍历到$a_i$时,取出堆顶,对堆顶的进行种操作

  1. 将当前元素接到堆顶元素的后面,即向堆顶加入$top + a_i$

  2. 将堆顶序列的最后一个元素改成$a_i$,即向堆顶加入$top - a_{i - 1} + a_i$

这样第$k$次取出的堆顶就是第$k$小的子序列和(如果要求第$k$大的子序列和,就用所有元素总和减去第$k$小的子序列和)

1 评论

用户头像
seelights   8个月前         踩      回复

大佬tql