JianRon
2022-03-15 20:51 北京师范大学 C++
关注
题意转化成：给一个数组然后找满足两个要求的最大的子段和，两个要求分别是:1、子段里的负数出现的次数不能超过m个，2、总和不超过K。
做法就是：转为前缀和数组pre_sum，m这个限制可以得到一个滑动窗口。在pre_sum上做这个滑动窗口，然后用一个带排序的可重集(在C++里是multiset)来维护窗口里的值。如果窗口的区间范围是[L,R]，那就在multiset里找不大于pre_sum[L-1] + k 的最大的值X，用这个X-pre_sum[L-1]来更新答案。
应该就是这样了，一开始想复杂了，结果最后想出来没时间写了):
查看原帖
3 评论
相关推荐
查看17道真题和解析 牛客热帖
更多
正在热议
更多
# 为了求职，我做过的疯狂伪装 #
6478次浏览 95人参与
# 从顶到拉给所有面过的公司评分 #
3169次浏览 53人参与
# 小红书校招直播来了 #
82390次浏览 478人参与
# 职场破冰，你们都聊什么？ #
2650次浏览 50人参与
# 晒晒你的中秋福利 #
13421次浏览 83人参与
# 聊聊这家公司值得去吗 #
542932次浏览 3627人参与
# 产品每日一题 #
59574次浏览 604人参与
# 你面试被问到过哪些不会的问题？ #
13181次浏览 559人参与
# 如何快速融入团队？ #
31025次浏览 278人参与
# 机械笔面试考察这些知识点 #
9260次浏览 89人参与
# 你觉得早上几点上班合适？ #
81226次浏览 329人参与
# 广联达求职进展汇总 #
9475次浏览 50人参与
# 电网笔面经互助 #
45323次浏览 428人参与
# 远景求职进展汇总 #
60241次浏览 317人参与
# 秋招报数：你投了多少家公司？ #
19308次浏览 204人参与
# 浪潮求职进展汇总 #
15378次浏览 131人参与
# 安克创新求职进展汇总 #
47183次浏览 496人参与
# 上班摸鱼，你都在干些什么？ #
4433次浏览 74人参与
# 为什么国企只招应届生 #
197264次浏览 1212人参与
# 机械人，你最希望上岸的公司是？ #
180863次浏览 1893人参与
# 秋招的嫡长offer #
18362次浏览 174人参与