携程笔试9.7
贴一个t4的做法:维护前缀和,遇到0加一,遇到1减一。对于每一个左端点来说,合法的右端点是这个区间的前缀和值都大于等于左端点的前缀和值。因此考虑记录每一个位置的前缀和值,查询时二分找到左端点的第一个小于左端点的前缀和值的位置,减一下就得到对应的区间对答案的贡献。时间复杂度O(nlogn)。
全部评论
这个 s = " " + s 学到了
请教一下:`查询时二分找到左端点的第一个小于左端点的前缀和值的位置` 前缀和数组不是升序数组,是怎么通过二分找到的?
我直接把前缀数组所有项加起来就过了,没二分查找
相关推荐
09-12 23:09
门头沟学院 嵌入式软件开发 小肥罗:此乃引蛇出洞之计,勾出你想去杭州的原因再告诉你不在杭州,让你打脸,自己离开。好一招抛砖引玉,虾仁猪心。你回复:计划去杭州,但我心中第一选择是宁波~巧了!
这计名叫“阿Q精神胜利法之厚脸皮不要脸我不尴尬谁爱尴尬谁尴尬去”之计!克制一切!
点赞 评论 收藏
分享
09-06 12:49
门头沟学院 Java 点赞 评论 收藏
分享