携程笔试9.7

贴一个t4的做法:维护前缀和,遇到0加一,遇到1减一。对于每一个左端点来说,合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值,查询时二分找到左端点的第一个小于左端点的前缀和值的位置,减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。
全部评论
这个 s = " " + s 学到了
1 回复 分享
发布于 2023-09-07 23:49 北京
请教一下:`查询时二分找到左端点的第一个小于左端点的前缀和值的位置` 前缀和数组不是升序数组,是怎么通过二分找到的?
点赞 回复 分享
发布于 2023-09-10 21:03 上海
我直接把前缀数组所有项加起来就过了,没二分查找
点赞 回复 分享
发布于 2023-09-08 13:45 江西

相关推荐

小肥罗:此乃引蛇出洞之计,勾出你想去杭州的原因再告诉你不在杭州,让你打脸,自己离开。好一招抛砖引玉,虾仁猪心。你回复:计划去杭州,但我心中第一选择是宁波~巧了! 这计名叫“阿Q精神胜利法之厚脸皮不要脸我不尴尬谁爱尴尬谁尴尬去”之计!克制一切!
这个工作能去吗
点赞 评论 收藏
分享
09-06 12:49
门头沟学院 Java
offeroffer...:我也是,前两面还挺紧张认真的,全程大脑飞速运转后面就越来越不想面了,不想说话不想思考
点赞 评论 收藏
分享
评论
6
9
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务