首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
基础学习课
实战项目课
求职辅导课
专栏&文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
れもんじゆん
2020-12-08 17:40
曲阜师范大学 C++
关注
已关注
取消关注
怎么快速求数列(A[i]+A[j])*(j-i)的最大值
注:1.数列的长度能达到1e6
2.j>i
提示
全部评论
推荐
最新
楼层
Maddison10
北京市十一学校
可以用李超树维护凸壳
10
回复
分享
发布于 2020-12-08 19:19
Maddison10
北京市十一学校
希望能对您有帮助
10
回复
分享
发布于 2020-12-08 19:20
Maddison10
北京市十一学校
这个李超树随便维护吧
9
回复
分享
发布于 2020-12-08 19:19
Maddison10
北京市十一学校
主要有一个A[i]*j的东西
9
回复
分享
发布于 2020-12-08 19:19
Maddison10
北京市十一学校
然后推式子化成kX+b的形式
9
回复
分享
发布于 2020-12-08 19:19
Maddison10
北京市十一学校
直接上李超树就ok了
9
回复
分享
发布于 2020-12-08 19:19
Maddison10
北京市十一学校
🤣🤣🤣
9
回复
分享
发布于 2020-12-08 19:20
Maddison10
北京市十一学校
您看看理解吗?
9
回复
分享
发布于 2020-12-08 19:20
Maddison10
北京市十一学校
😂😂😂
9
回复
分享
发布于 2020-12-08 19:20
Maddison10
北京市十一学校
😁😁😁
9
回复
分享
发布于 2020-12-08 19:20
牛客407119042号
复旦大学 算法工程师
由于同时和a[j]和j有关所以不能单纯维护当作斜率相关的问题来做 本问题是经典的决策单调性问题。 考虑我们选择j时如果j1>j2且a[j1]>a[j2]显然j2时候不如j1,因此我们用单调队列筛掉这些不符合条件的j2,最后得到一个单调下降子序列。 同理,选择i时如果i1<i2且a[i1]>a[i2]显然i2时候不如i1,帅选后i的选择区域也将在一个单调上升子序列中。 现在在一个单调上升子序列中选择i,一个单调下降子序列中选择j。 接下来考虑j对i1和i2的值f(i1,j)=(A[i1]+A[j])*(j-i1),f(i2,j)=(A[i2]+A[j])*(j-i2)作差 不妨设i1>i2 f(i1,j)-f(i2,j)=j*(A[i1]-A[i2])-(A[i1]*i1-A[i2]*i2)-A[j]*(i1-i2) =(A[i1]-A[i2],i1-i2)·(j,-a[j])-(A[i1]*i1-A[i2]*i2) 显然,随着j的增大f(i1,j)-f(i2,j)单调递增,也就是说,对于任意i1,i2存在一个在j0之后 (f(i1,j)-f(i2,j))*(j-j0)>=0 故我们在i待选择的单调上升子序列中的每个相邻元素计算其分界的j即可。具体实现就是用一个单调栈维护每个分界点,每次对相邻两个元素二分其分界点,然后维护单调栈。 1.得到i的候选序列I={i1,i2...ip} 2.得到j的候选序列J={j1,j2...jq} 3.初始单调栈s为空 4.枚举x,根据f(ix,j)-f(ix+1,j)的算出分界点jx,将jx比栈顶元素小,不断把元素踢出,然后加入jx 5.根据单调栈中的元素,得到每个序列J最优的决策ix,计算,并求最大值。 PS:这个问题转化称这样可能更好理解,二维的点集A={(i,a[i])},B={(i,-a[i])},在A中取一个点,在B中取一个点,最后要求其面积最大,当然最后做法本质没区别
3
回复
分享
发布于 2020-12-08 21:25
happypeople
湖南工业大学 C++
(A[i]+A[j])*(j-i) = A[i]*i - j*A[j] 很明显,j*A[j]是一个定值,枚举i=[1,n],然后记录前缀最小的 j*A[j]就行了
点赞
回复
分享
发布于 2020-12-08 18:27
还没有回复哦~
相关推荐
昨天 19:32
江西理工大学 Java
去哪儿一面凉经(40min)
约的 9.26 下午4点,面试官还算准时(看到别的同学等半天都看不到面试官) 自我介绍后,简单讲一下项目是怎么做的(挑了实习项目) 项目中是如何使用定时任务的,怎么简化的存储设计? 项目中是如何使用 Redis 订阅发布实现缓存的实时刷新? 讲一讲 MySQL 里面的事务 一般什么场景会用到事务? 事务是如何实现的? Redis 锁是如何实现的? 算法题:LeetCode 143.重排链表(一遍过,爽) 都答出来了,主要是前面项目讲了挺久的,面试官说我描述方面可以再精简一些 hh 全程下来面试官那边声音嘈杂,还是在面试官戴了耳机的情况下,现场情况可想而知。。...
投递去哪儿等公司10个岗位 >
去哪儿求职进展汇总
点赞
评论
收藏
分享
09-24 16:48
门头沟学院 机械设计/制造
美团二面后多久出结果
9.14二面,到今天完全没消息,这是不是就是凉了
美团求职进展汇总
你收到了团子的OC了吗
点赞
评论
收藏
分享
09-13 15:54
南京工业大学浦江学院 Java
邮件都能标题党,逆天。真**要气死了
自来熟的放鸽子能手面试中:
绷不住了
点赞
评论
收藏
分享
09-26 19:55
西安工业大学 嵌入式软件工程师
经纬恒润二面
这个是啥意思?
投递经纬创投等公司10个岗位
点赞
评论
收藏
分享
09-25 11:34
华中科技大学 C++
好像人活着就没有一刻能闲下来
三四五月找实习找得心力交瘁,每天背八股刷题刷得想吐,结果面了一堆kpi面,心态接近崩溃,万幸在要结束的时候碰巧找到了大厂实习,以为可以歇一段时间好好休息一下了,接下来有实习经历秋招应该也会顺利很多了。结果七八月很多提前批正式批都开始了,可🐀刚来实习没多久,组里业务、公司基建都没怎么摸清,每天还是打杂,简历上实习经历都不晓得怎么写。每天上班都够累了,下班回挂逼出租屋往床上一躺,根本没心思投简历、看八股、刷题。加上看别人说提前批也是跟正式批一起排序就没怎么关注,准备歇到九月才开始投。躺到听到同门oc三家大厂的消息才猛然惊醒,三天投了五十家,一个月快过去了,就面了三家,两家kpi速通一面挂,大部分...
超脱的斜杠青年在查重:
中国人一辈子都在内卷,***自己人
点赞
评论
收藏
分享
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
面试反问环节怎么问!看这一篇就够了!
1.7W
2
...
秋招公司犯下的“七宗罪”
8019
3
...
🧧央国企笔面经全网征集令!
7533
4
...
好像人活着就没有一刻能闲下来
7047
5
...
放弃敲代码做产品经理
6004
6
...
兄弟,我在快手逆袭了!(读博签证被拒后......
4869
7
...
蚂蚁,是我太菜了
4681
8
...
也不知道是因为我只是硕士学历,还是因为我不是男生,亦或者是因为我本科学校只是个211不管我研究生多么拼命,发了多少论文和专利,拿了多少奖学金,干了多少重点项目在茫茫简历中,依然不是被认可的那一个即使有
4562
9
...
怎么a薪资
4538
10
...
0Offer
4508
正在热议
#
你的秋招简历被谁挂了?
#
65668次浏览
971人参与
#
你觉得今年秋招难吗
#
804848次浏览
10944人参与
#
同程秋招
#
11922次浏览
185人参与
#
国央企求职进展汇总
#
12044次浏览
60人参与
#
宁德时代求职进展汇总
#
64678次浏览
523人参与
#
比亚迪求职进展汇总
#
350942次浏览
1976人参与
#
建信金科校招
#
18352次浏览
241人参与
#
选完offer后,你后悔学机械吗?
#
6726次浏览
42人参与
#
通信硬件投递记录
#
277718次浏览
6370人参与
#
大厂还是考编
#
62492次浏览
1217人参与
#
机械制造投递记录
#
1106809次浏览
21696人参与
#
想实习转正,又想准备秋招,我该怎么办
#
387698次浏览
4112人参与
#
非技术投递记录
#
262525次浏览
4008人参与
#
产品薪资爆料
#
67913次浏览
717人参与
#
如何一边实习一边秋招
#
830098次浏览
11113人参与
#
谈薪时HR压价该怎么应对
#
80163次浏览
949人参与
#
毕业季,你想好怎么跟生活对线了吗?
#
108979次浏览
2527人参与
#
双非本科求职如何逆袭
#
404482次浏览
5158人参与
#
OPPO求职进展汇总
#
458412次浏览
4089人参与
#
找实习多的是你不知道的事
#
1184865次浏览
17003人参与
#
0offer是寒冬太冷还是我太菜
#
675759次浏览
6482人参与
#
如果实习可以转正,你会不会放弃秋招
#
122572次浏览
1758人参与
牛客网
牛客企业服务