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 评论
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 大厂VS公务员你怎么选 #
42315次浏览 511人参与
# 产品实习，你更倾向大公司or小公司 #
175390次浏览 1990人参与
# 未岚大陆求职进展汇总 #
21666次浏览 100人参与
# 发面经攒人品 #
2662353次浏览 36198人参与
# 一汽大众工作体验 #
11229次浏览 23人参与
# 26届秋招公司红黑榜 #
742次浏览 3人参与
# 平安产险科技校招 #
1613次浏览 0人参与
# 参加完秋招的机械人，还参加春招吗？ #
66959次浏览 596人参与
# 最难的技术面是哪家公司？ #
52779次浏览 880人参与
# 机械人的工作环境真的很差吗 #
23339次浏览 117人参与
# 来聊聊机械薪资天花板是哪家 #
145828次浏览 804人参与
# 我对___祛魅了 #
133887次浏览 743人参与
# 你有哪些缓解焦虑的方法？ #
36114次浏览 829人参与
# 关于提前批我想问 #
242224次浏览 2284人参与
# 你现在会用到哪些AI技能？ #
12041次浏览 102人参与
# 职场捅娄子大赛 #
428958次浏览 4161人参与
# 我的求职进度条 #
117209次浏览 1403人参与
# 经纬恒润求职进展汇总 #
135619次浏览 1059人参与
# 机械制造公司评价 #
147986次浏览 347人参与
# 通信硬件2023笔面经 #
42294次浏览 287人参与
# 你还有多少年退休？ #
27773次浏览 192人参与
# 华为工作体验 #
233590次浏览 1285人参与