【每日一题】5月15日题目精讲

题号 NC14683
名称 储物点的距离
来源 牛客练习赛8
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

因为在数轴上,求任意两个点的距离只需要先维护一个距离的前缀和就行了。同理求某个区间内物品数量也可以前缀和。
如果我们固定了目标点是很简单的,再求个前缀和就行。但是这里的目标点显然需要枚举——我们并不希望枚举的时候在每一个目标点都算一遍整个区间。我们来考虑目标点从i右移一位到i+1的时候会发生什么变化——如果[l,r]在i和i+1右边,显然[l,r]当中的每个物品都少移动了i到i+1的距离,只需要在i点的答案基础上减去[l,r]的物品总数乘i到i+1的距离就行了;如果i和i+1在区间右边那就是减去,如果在中间,就是i+1左边的那部分加上区间中物品个数乘以距离,右边部分减去。
于是求解就变成O(n)的啦(算以每个点为目标点都是O(1)的)!。

我们可以考虑先求出前i个地方的物品全部搬到0的代价,这样就可以求出某个区间全部搬到0的代价了。

看完邓老师的题解,记得自己去做题提高呀~
欢迎各位大佬来做题写题解,也欢迎大家踊跃在当日讨论贴中提问!

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目5月22日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/8fdd45d64f3849f4bf3de88b78a3dfe2
1 回复 分享
发布于 2020-05-14 22:32
https://blog.nowcoder.net/n/c9386428ae874a0b941a779679881188
1 回复 分享
发布于 2020-05-14 21:00
https://blog.nowcoder.net/n/20495953c88244718423d6f011f373dd 12点前
点赞 回复 分享
发布于 2020-05-22 10:51
https://blog.nowcoder.net/n/6ce4f0f22c8643bcb323942f746a3347 赶到截止前了
点赞 回复 分享
发布于 2020-05-22 08:45
https://blog.nowcoder.net/n/483539cf61d1483488807c163233d179
点赞 回复 分享
发布于 2020-05-20 18:49
https://blog.nowcoder.net/n/7ac86549e15a4c428522c3f5f1fa469c
点赞 回复 分享
发布于 2020-05-16 22:03
https://blog.nowcoder.net/n/fe0c3e1153f14dab8951b659cef41478
点赞 回复 分享
发布于 2020-05-16 20:13
https://blog.nowcoder.net/n/6f2e208c59d44a02803fa02c50c8209c
点赞 回复 分享
发布于 2020-05-16 19:04
https://blog.nowcoder.net/n/6a4294755a1542dbb25cdc8b4018b9bd
点赞 回复 分享
发布于 2020-05-15 19:27
https://blog.nowcoder.net/n/ea427cec8f2f4431a0267db6f15ae096
点赞 回复 分享
发布于 2020-05-15 18:19
https://blog.nowcoder.net/n/9305734f89d64e47ad0a9015b420f62a
点赞 回复 分享
发布于 2020-05-15 12:23
https://blog.nowcoder.net/n/a4e6ede6ae12411387e77290bd79e5de
点赞 回复 分享
发布于 2020-05-14 21:09
https://blog.nowcoder.net/n/9046a91ea872429e94072f6d816df4cb
点赞 回复 分享
发布于 2020-05-14 20:56
https://blog.nowcoder.net/n/2762de8ca9e04ad199f3aa506f402311
点赞 回复 分享
发布于 2020-05-14 19:17
https://blog.nowcoder.net/n/d012e0ef33cf42a89fe1567339b7b7e5
点赞 回复 分享
发布于 2020-05-14 15:22
https://blog.nowcoder.net/n/656cf9f7d91a46ddaff7408764334009
点赞 回复 分享
发布于 2020-05-14 14:52
https://blog.nowcoder.net/n/05c19dacf42e4f07942e15d4999f9ea8
点赞 回复 分享
发布于 2020-05-14 14:44
https://blog.nowcoder.net/n/eb62543cb8ab4169b64bbfa5ec2178bf
点赞 回复 分享
发布于 2020-05-14 12:37
https://blog.nowcoder.net/n/4cbf7665a50f40308b0a3941618dc1ec
点赞 回复 分享
发布于 2020-05-14 12:04

相关推荐

04-08 23:14
已编辑
南阳理工学院 算法工程师
本人情况:26届双非本科,两段实习经历,目前拿到的都是实习的offer,一个校招的都没有,他们都说先实习,然后等拿到毕业证了直接转正,我又害怕干三个月给我叉出去面试题也发一下吧### 杭州问尔信息技术后端登录你是怎么做的?JWT令牌你了解过吗?他虽然是一段字符串,他表达了什么东西?怎么解析出来信息和过期时间?JWT令牌怎么续期?如果我拉黑一个账号,要怎么做?两种方案(有无redis)mongodb和mysql的区别?mongodb和mysql分别实用于什么项目?选型你会怎么选?数据库的事务,那些地方需要使用,那些地方不需要使用?他会影响什么性能?mysql和pgsql有什么差异你知道吗?消息队列 redis也有,为什么要用mq?前后端会部署吗?docker会用吗?内部通信前端 async和 await你知道吗?异步编程的原理是什么?vue3 为什么你改变一个字符串 前端会跟着改动AI工具会用什么?你会怎么用?### 仲财通常用的锁有哪些synchronize和ReentrantLock的区别分布式锁了解吗?分布式事务mysql表字段sql优化什么时候用索引索引什么时候会失效mysql事务ioc一些项目应用问题### 观妙科技项目问题...zset的架构是什么样子的线程池突然队列被打满了怎么办?如果上游和下游都无法控制,该怎么维护select * from user where age>20 order by update_time 索引设计检索过程是什么样的冒泡排序和快排,有什么区别怎么判断链表有没有环### 观妙科技-二面项目部分...线程池的核心参数有哪些你是怎么用线程池的JMMG1模型跳表介绍一下平衡二叉树TCP为什么要三次握手?说一下hashmap红黑树的特征你有什么学习的方法
牛马人的牛马人生:对学院本而言很强了
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

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