【每日一题】4月22日题目精讲 二分

题号 NC14301
名称 K-th Number
来源 CCPC.2017哈尔滨站-重现赛
戳我进入往期每日一题汇总贴~
往期每日一题题单

图片说明

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

题目让对数列A的每个区间求第K大,并将第k大插入到B中,再求B的第M大。
按题目一个区间一个区间求是肯定不行的,两次第k大十分丧病。
我们可以考虑把求值变成验证——
首先二分答案,每次二分的时候我们得到一个x,这个时候我们利用尺取,去得到第K大数大于x的区间一共有多少,如果大于m-1个说明x取小了。
那么第k大数大于x的区间一共有多少怎么求?第k大数大于x的其实也就是大于x的数至少有k个,当我们枚举区间左界L,我们可以从L往右扫描到第一个大于x的数有k个的的点R,右界在这个位置及其之后的区间大于x的点的个数都大于等于k个。而当L右移一个位置,R显然只会右移不会左移,所以L和R对每一个数字都只访问一遍,这样,时间复杂度是 的了。加上二分就是 了。

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

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
占坑啦啦啦~
1 回复 分享
发布于 2020-04-21 11:06
https://blog.nowcoder.net/n/801416646e5140f29d6071c655c5c45a  持续补题,持续wa
点赞 回复 分享
发布于 2020-05-04 15:55
https://blog.nowcoder.net/n/84bc4e7b890248f496380d620a4239ed
点赞 回复 分享
发布于 2020-04-29 11:24
https://blog.nowcoder.net/n/554842b6d25149ac8a20a01a2986f0b9 
点赞 回复 分享
发布于 2020-04-29 00:42
https://blog.nowcoder.net/n/646fbd13aa2f42e09985d37353ef2829
点赞 回复 分享
发布于 2020-04-28 20:47
https://blog.nowcoder.net/n/87960aacbe454e02b1ca011b33636e30终于搞明白了
点赞 回复 分享
发布于 2020-04-27 23:18
https://blog.nowcoder.net/n/2bd9c4f1710e4150bcf61a784355a421
点赞 回复 分享
发布于 2020-04-24 15:47
https://blog.nowcoder.net/n/ddc1b7761e9c472bac70079dcd04f3c7 其实看着简单 但是挺难想到的?~~~我太弱了~~~
点赞 回复 分享
发布于 2020-04-23 21:58
https://blog.nowcoder.net/n/11a6a92bb91a4710b47d09fe936c75e1
点赞 回复 分享
发布于 2020-04-23 19:28
https://blog.nowcoder.net/n/8f617d2f43f14928a54c6a08f80f25ea
点赞 回复 分享
发布于 2020-04-23 13:35
https://blog.nowcoder.net/n/3ce47756ce7f48e997fab2cf124ed0fd 
点赞 回复 分享
发布于 2020-04-23 11:59
https://blog.nowcoder.net/n/79eab894e8a94f19b0b40ece88bfa744
点赞 回复 分享
发布于 2020-04-22 18:05
https://blog.nowcoder.net/n/d78220c8048548acbd81a9fcd1391f0c 看了一天终于学会了
点赞 回复 分享
发布于 2020-04-22 16:09
https://blog.nowcoder.net/n/d1ae407421844a43a87b1c341e159596
点赞 回复 分享
发布于 2020-04-22 00:34
https://blog.nowcoder.net/n/c6c4f2762c4142f29300819449c3a732
点赞 回复 分享
发布于 2020-04-21 22:05
https://blog.nowcoder.net/n/08cbadc2b29442aea97f1186ebaf06e2
点赞 回复 分享
发布于 2020-04-21 21:59
https://blog.nowcoder.net/n/f144ab125c4843c7a6a78a1c43138e89
点赞 回复 分享
发布于 2020-04-21 21:10
https://blog.nowcoder.net/n/fbc3499dbd9b4de4bfd89f813933d01a
点赞 回复 分享
发布于 2020-04-21 19:57
https://blog.nowcoder.net/n/1a942266619443c882f376a116e60f2d 
点赞 回复 分享
发布于 2020-04-21 19:13
https://blog.nowcoder.net/n/0e7673e4780b4059a5fb14a1f289e8d0    这题好难,搞了我好久
点赞 回复 分享
发布于 2020-04-21 17:24

相关推荐

今天提了离职,领导说让我离职前请几位正式工吃饭……我本来是有请客的打算的,因为感觉这几个同事人还挺好,想以后维持一下关系。但我第一次听领导主动说让实习生请客的……(只因为一个请客,倒不至于发个帖子。主要是这个公司的离谱事情太多了,跟之前的实习感受完全不同)之前几段实习,在实习结束前,mentor或领导会请客欢送,无论是私下吃个便饭也好,还是全部门的奶茶也好。这几位正式工既不是我的mentor,也不是我的领导。而且我异地实习生活很拮据,这家公司给得很少。当然了,这也算意料之外,情理之中。这家公司一直对实习生很不友好。经常让实习生加班,总是跟实习生说“辛苦一下”。你也没给我那个辛苦钱啊!晚上干到12点,周末加班干,要么是领导要看,要么是客户着急。之前的公司,我主动加班,mentor都会跟我说,实习生不用加班,到点下班就行。加班就算了,我安慰自己就当学东西了,锻炼抗压能力。但辛苦完了,节日的福利,竟然只有正式员工才有?!我之前实习,实习生的节日福利一点也不比正式工少啊……有的正式工还会把福利分给实习生一部分。挺心寒的……而且,我觉得这家公司对实习生很不负责,纯拿你当廉价劳动力。可以让刚毕业才工作三个月的人带实习生,实习生不会的,正式员工也不会,俩人就一起探索。还真就那个“和公司共同成长”😅避雷某GJ级专精特新小巨人企业,六百多人,整体氛围挺离谱的,跟我去过的其他公司完全不一样。领导都是些老东西,喜欢PUA,爹味十足。流程混乱、管理混乱、代码混乱、职责混乱,技术领导不懂技术,总说出一些可笑的畅想。虽然技术不咋地,但是把产品技术路线吹上天的本事倒是有,而且很大!什么xx系统、xx模型、xx工具,名字一个比一个高大上,其实可能就是调用Qwen、DeepSeek、Doubao……还声称这两年要上市,我祝你们成功吧😄
不知道怎么取名字_:实习的能有多少钱,为啥要请客
点赞 评论 收藏
分享
01-04 07:53
门头沟学院 C++
心愿便利贴:工作了以后回头再看待这个问题,从客观的视角来讲是因为每个人对自己的要求不同,学习好的人对自己的要求很高,所以觉得考不好就天塌了,认为自己学习好并且值得一份好工作的人也是一样,找不到符合自己预期的工作肯定也会觉得是侮辱,牛客上有很多名校大学生,肯定会存在这种好学生心态啊,“做题区”从来都不是贬义词,这是大部分普通人赖以生存的路径,这个有什么好嘲讽的,有“好学生心态”没有错,但是不要给自己太大的压力了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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