由于同时和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 2

相关推荐

bg:双非本,一段中小厂6个月测开实习今天发这个帖子主要是想聊一聊我秋招以来的一个发展我是在8月底辞职,打算秋招,可是看网上都说金九银十就想着自己就是一个普通本科生,现在九月份都是一些大神在争抢,所以9月份基本上没投,等到了10月份才开始秋招,可是这个时间好像已经有些晚了,今年秋招开启的格外早,提前到了7,8月份,我十月才开始,官网投了很多公司,没有任何一个面试机会,这个情况一直到了十月底才有了第一个面试,当时没有面试经验,所以不出意外的挂了后续就是漫长的投递,但是毫无例外没有面试,没有办法我只能另辟蹊径开始在BOSS上边投递,然后顺便也根据BOSS上边这个公司名称去浏览器搜索看看有没有官网投递渠道,毕竟官网上投递后还是可以第一时间被HR看到的,然后一直不停投递,一开始第一个星期基本上都是投的正式秋招岗位到了第二个星期才开始实习和正式一起投,到十一月底的时候已经沟通了700➕才有一共1个正式的,5个要提前实习的,3个实习的面试,最后结果是过了1个要提前实习的和2个实习的每次面试我都会复盘,发现这些小公司面试官问的五花八门,有的专问基础,有的专问项目,有的啥都问,不过自己也是看出来了一下门道,就是小公司不像大公司面试官那样能力比较强基本上你简历上边的他都会,然后会根据简历来问,小公司面试官他们更多的是看自己会什么,然后看看你简历上边哪些他也是会的然后来问,经过不断的复盘加上背各种各样面试题,到了11月底12月初才有了1个要提前实习的offer还有2个实习的offer,而且薪资待遇对我来说已经很可观了可是啊,人总是这样得了千钱想万钱,我又开始不满现状,但是此时的我面试能力经过这么多面试和复盘已经很强了,然后在十二月份运气爆棚,被极兔和小鹏补录捞起来面试,还有个百度测开的实习面试,这个时候因为有了offer所以感觉有了底气,面试也很自信,最后结果是全部都过了那个时候我感觉自己真的很厉害,我问了极兔那边的HR像我这样的双非本收到offer的在极兔有多少?他告诉我产研岗90%都是硕士,10%里边基本上都是211,985,想我这样的很少很少,那一刻感觉自己超级牛逼,小鹏就更不用说了,最后也是不出意外选择了小鹏所以我就我个人经历想对和我学历履历差不多的牛友一些建议第一:秋招一定要趁早,真到了9,10月,那个时候可能你投的结果可能还不如7,8,11月,第二:最好先拿小公司实习或者正式练练手,提升一下面试能力,我个人觉得因为小公司问的五花八门所以你会更加横向去提升自己能力,而且大公司其实面试没有那么难,除了一些非常卷的岗位,公司大神比较多会问的很难,一般好点的公司都不会问的那么难,他们也知道都是应届生不会要求那么高第三:当有一定能力后,就是坚持了,对于我们这样的学历,没有特别强的履历情况下,就是要抓住提前批和补录的机会,这个时候各方面不会卡的很严,是我们很好很好的一个机会第四:就是运气也是很重要的一部分,不过这个很难去说什么最后祝各位牛友都能收获自己满意的offer😁😁😁
秋招,不懂就问
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务