子序列&&子串 - AcWing

Loading [MathJax]/jax/output/HTML-CSS/jax.js

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

子序列&&子串

作者：

橙外 , 2024-03-09 10:48:47 , 所有人可见 , 阅读 58

2

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

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

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

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

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

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

1 评论

seelights 2024-03-09 21:30

回复

大佬tql

1024

x