【每日一题】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-24 13:51
已编辑
西安电子科技大学 Java
👋个人背景:211计算机混子,代码能力一般,春招急头白脸参加央国企最后拿下这两个offer👏offer1:中广核工程公司驻陆丰仪控调试,待遇19+4,离家1800km💯offer2:张家口卷烟厂待遇未知,应该有13个(猜测),离家500km牛油们帮忙选一下,家里人不是很喜欢卷烟厂这个offer,但是蜀黍烟草局下岸了
鸿雁于飞:先说offer1:中广核工程公司驻陆丰仪控调试(待遇19+4) 中广核这艘央企大船还是很稳的,集团综合效益稳居央企前列。但你得搞清楚,这个19+4的"19"是总包,不是到手数——招聘宣传待遇里把所有能算的都算进去了,饭卡福利积分啥的全包含,有牛油分享实际到手大概打七折。试用期到手可能就四五千的水平,转正后基本工资4800左右,其余靠绩效、年终、大修费撑着。不过核电的工作环境有点"牢笼感"——核电站位置偏僻,远离繁华都市。工程公司是承包商性质,干活比业主公司累,而且大概率要经常出差,有的岗位年出差天数100天以上。最大问题是你这1800km的距离过于离谱,核电员工工作强度最小的时候一周也就回一次家,离得远回家成本高,夫妻感情和亲子关系都是现实考验。说白了:高薪是拿青春和生活换的。 再来看offer2:张家口卷烟厂(待遇约13个) 张家口卷烟厂是河北中烟下属三家卷烟厂之一,河北中烟主打的"荷花"系列连续多年位居全国高端卷烟品牌销量前列。烟草系统薪资由基本工资+绩效+年终奖构成,综合年薪普遍显著高于当地平均水平,六险二金齐全,福利拉满。有人问"13个是不是太平平无奇了"——关键张家口是四线城市,生活成本低,这13万的购买力相当于深圳的二十多万。离家500km,开车半天到家,周末回趟家完全可行,幸福感直接上两个档次。中广核的牛油说了句大实话: "哪个核电站好?永远是离家近的那个最好。" 选烟厂同理。 但是,卷烟厂的坑你得清楚: 首先卷烟厂和烟草局不一样,卷烟厂是生产操作类岗位,很多要三班倒。报考条件明确写了要能"胜任夜班工作和长时间站立工作"。一线操作工每天盯着流水线卷烟,工作内容高度重复,有入职的人描述为"食之无味弃之可惜"。有牛油直言"卷烟厂和商业性质的烟草公司不一样,前者很坑很累"。其次你家里人不是不喜欢,而是担心你这211计算机科班出身,进了烟厂干操作工,技能会快速退化,未来如果行业改革,技术壁垒不高,转行比较困难。等你干两年再跳出来,技术栈全忘干净了,回头再去敲代码,发现连应届生都卷不过。 老牛油的灵魂三问: 1. 你是更怕穷,还是更怕想家? 如果特别恋家的人跑1800km之外,第一年哭鼻子的概率高达80%。陆丰那地方偏僻单调,核电基地又远又闷,闲下来除了打游戏没啥娱乐,社交圈也窄。找个对象都费劲——牛油亲测核电站"狼多肉少"。 2. 你的代码能力有多"一般"? 如果真的一般,仪控调试和你专业匹配度不算高,这活儿主要是工程改造设计、现场实施管理、在建机组设计审查等,偏工程向而非纯软开。干两年后跳回互联网赛道,竞争力不一定有明显提升。反倒是烟厂不需要你写代码,进去就是稳定躺平。 3. 烟草局下岸这事儿会不会让你耿耿于怀? 如果烟草局是你第一志愿,烟厂只是plan B,那得想清楚:进去了可能每天看着天花板想"如果当初去了烟草局该多好",这种内耗比钱少还折磨人。如果你能接受"反正都是烟草系统,先进去再说"的心态,那倒无所谓。 一句话总结: 如果年轻想拼想闯做技术积累,中广核虽然累和远,但简历上央企核电的金字招牌确实有含金量,加上到手收入在这两个选项里确实更高,考虑到你个人经济情况和家庭状况,假如家里不需要你常回去照顾,家里有兄弟姐妹帮手分担,那先去核电待三四年,积累经验再跳槽也不失为一步棋。 如果想安稳过日子离家近当"人上人",烟厂低线生活成本加持,加上稳定的编制和福利体系,在张家***得滋润,幸福感吊打陆丰。尤其家里人是那种离不开你的,有烟厂的稳定且离家近,比任何高薪都实在。
点赞 评论 收藏
分享
评论
1
2
分享

创作者周榜

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