首页 > 超级钢琴
开通博客写题解
头像 sunny_forever
发表于 2021-08-11 20:06:23
ST 表 + 优先队列 + 前缀和 题意 给一个长度 为 n 的序列，让你从中选 k 个长度在 [L,R] 范围内的区间 (同一个区间不可选多次) 要求：这 k 个区间的区间和 相加 得到的值 应该最大 思路 (1):求出前缀和 (2):枚举 i 令其作为区间左边界，则右边界ri可取值 [i+L- 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 钱逸凡
发表于 2020-11-04 13:52:25
解题思路 用到的知识点：st表+堆 思维过程 按照题目的要求，我们要求所有长度为[l,r]的子区间中最大的k个，首先，我们不可能遍历所有的子区间，因为那是O（n^2)的，我们考虑贪心 先考虑k==1时： 当k=1，我们只需要找最大的一个子区间，但是，这也要遍历所有子区间，于是考虑如何用较小的时间找出 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 芙蓉王媛
发表于 2022-09-03 11:07:29
小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。 这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。 一个“超级***”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级** 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”