关注
题意转化成:给一个数组然后找满足两个要求的最大的子段和,两个要求分别是: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-12-22 16:53
大连理工大学 产品总监
王海:不算mentor但也带过几个实习生,直接观感就是你可以摸鱼可以想早下班,分给你的工作好好完成就行 点赞 评论 收藏
分享
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 春招什么时候投? #
5094次浏览 76人参与
# 春节提前走,你用什么理由请假? #
4948次浏览 107人参与
# 春节前,你还在投简历吗? #
7164次浏览 94人参与
# 实习到现在,你最困惑的一个问题 #
1901次浏览 56人参与
# 牛客AI体验站 #
13346次浏览 253人参与
# 牛友的春节生活 #
1658次浏览 56人参与
# 备战春招/暑实,现在应该做什么? #
1655次浏览 53人参与
# 从夯到拉,锐评职场mentor #
1555次浏览 31人参与
# 聊聊Agent开发 #
14444次浏览 363人参与
# 距离春招还有一个月,你现在是什么开局? #
2918次浏览 53人参与
# 推荐一个值得做的AI项目 #
3931次浏览 125人参与
# 暑期实习什么时候投? #
3574次浏览 84人参与
# 实习想申请秋招offer,能不能argue薪资 #
218564次浏览 1171人参与
# 腾讯工作体验 #
566921次浏览 3700人参与
# 哪些瞬间让你真切感受到了工作的乐趣 #
24442次浏览 105人参与
# 通信硬件2024笔试面试经验 #
269160次浏览 2053人参与
# 实习必须要去大厂吗? #
188501次浏览 1767人参与
# 正在春招的你,也参与了去年秋招吗? #
349911次浏览 2590人参与
# 双非本科的出路是什么? #
208704次浏览 1566人参与
# 最难的技术面是哪家公司? #
65407次浏览 971人参与
查看8道真题和解析