【每日一题】6月11日题目精讲 枚举

题号 NC17315
名称 背包
来源 Wannafly挑战赛20
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

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

题解

求中位数最大其实并不是动态规划(就算能动态规划这个题的数据范围也是不允许的),我们考虑去枚举这个中位数x,分奇数偶数讨论。
如果m的奇数的话,枚举中位数x,x的左边(小于等于他的)有m/2个物品,右边也要选m/2个物品。左边的m/2个和右边的m/2个显然都是选体积最小的。我们用优先队列维护左右两边已放的物品各自m/2个物品,如果背包爆掉了,就把体积最大了拿出来看能不能换掉,换不掉就不行了。
m是偶数发情况会稍微麻烦一点——因为有两个数都与中位数有关,而复杂度不允许我们都去枚举这两个数,只能选择其中一个去枚举,我们枚举大的那个(其实枚举哪一个都是可以的),左边和右边的最小的m/2-1个数的和还是用一样的方法维护,第m/2个数(也就是两个中位数中小的那个)则需要在前面选一个不会把背包撑爆的最大的,用一个二分查找即可。

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

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
1 回复 分享
发布于 2020-06-10 12:13
https://blog.nowcoder.net/n/62684f06d46f41ba80e7a91dd05d48af
点赞 回复 分享
发布于 2020-06-16 16:04
没有发现右半部分的单调性,用线段树莽过的。 https://blog.nowcoder.net/n/d903bd54623b4760b10009c43103519d
点赞 回复 分享
发布于 2020-06-16 15:06
https://blog.nowcoder.net/n/b3956e3473054d45b90ae6f10862edc8
点赞 回复 分享
发布于 2020-06-16 12:29
https://blog.nowcoder.net/n/a61425eaf3514cacac55e961b97cf8a6
点赞 回复 分享
发布于 2020-06-15 11:31
https://blog.nowcoder.net/n/23bfb56576cf4965babf5d4035928c68
点赞 回复 分享
发布于 2020-06-12 11:01
https://blog.nowcoder.net/n/e69c6bd5822041d98a0cab1b1bc758e2
点赞 回复 分享
发布于 2020-06-11 11:38
https://blog.nowcoder.net/n/90a4711d69b34a9ca07e7c08b14ea225
点赞 回复 分享
发布于 2020-06-11 08:37
啦啦啦ac了  https://blog.nowcoder.net/n/0c38bb3ea24042a797926f326778fc0d
点赞 回复 分享
发布于 2020-06-11 00:07
https://blog.nowcoder.net/n/993b9dca61e34a8dae28e833f50f6b8d
点赞 回复 分享
发布于 2020-06-10 21:36
https://blog.nowcoder.net/n/00f72b73795045a6868ba4f19dcb2ff5
点赞 回复 分享
发布于 2020-06-10 17:38
https://blog.nowcoder.net/n/3da5a8df784f4fec839be49f333d3ada
点赞 回复 分享
发布于 2020-06-10 16:46
https://blog.nowcoder.net/n/eb4c60f401e74f1ca3306167f4ef429e
点赞 回复 分享
发布于 2020-06-10 14:56

相关推荐

04-20 22:20
已编辑
门头沟学院 golang
27届,bg为四非本211硕,如题,导师不放实习,且每周至少一次线下组会(工作日),从研一上开始实习,然后我组在研一下引入了打卡机五段大厂分别是:美团到店、美团服务零售、快手电商、字节TikTok、字节CapCut。目前要结束我的第五段实习了(不会再刷第六段,好好搞学校的事,还有秋招)本来一直告诉自己的是“所有委屈到了终点再说”,过去告诉自己的终点自然还没到,但我觉得自己仿佛已经到了另一个终点,有感而发,写了这篇文章也许你会觉得为啥不尝试问问导师能不能实习,或者用其他让自己舒服的手段,我只能说,这很复杂,有导师的人自然会懂,这种一开始就把“利益冲突”摆明面上的招几乎就是不可能成功———————————————————我到底是怎么实习的?骗hr自己满勤,然后没有捷径,就是每周往返,第一段去的是北京美团,而学校在江苏,因此需要一周一次北京江苏往返,因为实习钱少,所以坐的基本是绿皮,难以入睡,下车后就是长达2小时的地铁去公司,地铁站上靠着人睡觉周末做什么?基本在做导师的科研or横向,学习的话很多时候就是尽力在晚上回到出租屋的时候学,这很难维持,但只能不断push自己如何破解打卡机?直接把打卡机偷了,或者使用指纹膜(当然我很早就做好了无法破解的准备,那就是找个长三角实习,每天早起去打卡完坐高铁去实习,从每周高铁往返变成每天)导师会压力吗?非常压力,实习的时候非常害怕微信弹出他的消息,PTSD了,有时候一周要往返两次学校,每次都跟要死了一样,之前真是情绪崩溃好几次,哈哈哈哈平时往返怎么平衡工作?我本来很晕车,为了不耽误公司和导师的进度,从车上一看电脑就头晕、吐,到后面可以随意在高铁、地铁、出租车上Coding,甚至不会再因为往返感到心累了,哈哈哈哈这一路已经淬炼出比较坚强的内心了,已经数不清多少次坐末班高铁从学校回公司,多少次凌晨6点爬起来赶车过去我会把这些当作是我人生的弯路,但现在,这些已经成为我宝贵的经验了。往后,我想我也能真正允许各种不好的情况出现了,因为我会真正把它当作我要解决的问题,而非抱怨,这又何尝不是终点呢?要照顾好身体,我不管怎么往返,一直非常在乎身体,会让自己睡够8小时,最近几星期培养早睡早起到公司健身后去工作的习惯,我觉得好身体很关键
gtgt..:很佩服,但是很恐怖,感觉已经从人类异化到高度运转的机器了
美团工作强度 2455人发布
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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