【每日一题】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. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴