关注
题意转化成:给一个数组然后找满足两个要求的最大的子段和,两个要求分别是: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 评论
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 2025年终总结 #
171345次浏览 2890人参与
# 找工作,行业重要还是岗位重要? #
85182次浏览 1687人参与
# 职场上哪些行为很加分? #
306589次浏览 3449人参与
# 大家每天通勤多久? #
69520次浏览 441人参与
# 你面试体验感最差/最好的公司 #
16689次浏览 275人参与
# 实习的内耗时刻 #
210928次浏览 1538人参与
# 一人说一个提前实习的好处 #
10016次浏览 200人参与
# 今年你最想重开的一场面试是? #
3775次浏览 67人参与
# 互联网行业现在还值得去吗 #
46856次浏览 351人参与
# 秋招落幕,你是He or Be #
10729次浏览 223人参与
# 面试吐槽bot #
164948次浏览 814人参与
# 实习没事做是福还是祸? #
16209次浏览 250人参与
# 重来一次,你会对开始求职的自己说 #
5767次浏览 143人参与
# 反问环节如何提问 #
126336次浏览 2663人参与
# 礼物开箱Plog #
622次浏览 21人参与
# 团建是“福利”还是是 “渡劫” #
6905次浏览 147人参与
# 工作中听到最受打击的一句话 #
6180次浏览 109人参与
# 我的第一份实习怎么找的 #
208480次浏览 1827人参与
# 比亚迪工作体验 #
74444次浏览 281人参与
# 大厂VS公务员你怎么选 #
74454次浏览 681人参与


