牛牛的揠苗助长

牛牛的揠苗助长

http://www.nowcoder.com/questionTerminal/70063f9318f9464e9340d8e0859085bc

方法:二分答案
合理性:假设K天能恰好能解决问题,那么K+1必然也行(可以把k+1天增长的那个用魔法减去),所以K天之后都是可以的。
现在二分答案:假设第K天可以,那么可以在O(N)的复杂度从a数组里得到不使用魔法的b数组。(例如 3 3 5 经过 2 天 变成 4 4 5)
然后现在考虑使用魔法,把b数组中每个值都变成了x,所需的魔法次数为|b1 - x| + |b2 - x| + ... + |bn - x|,考虑到贪心,只要上述公式的最小值小于等于K次魔法就可以,所以第K天是否成立的依据是 |b1 - x| + |b2 - x| + ... + |bn - x| 的最小值(x为数轴上任意一点) <= K。
x取b数组中位数时取到最小值。

全部评论

相关推荐

1、自我介绍2、Agent项目是实习项目还是个人项目?有没有上线?3、拷打实习(10min)4、大模型微调,你的训练数据集是如何构建的?数据量有多大?5、在构建数据集的过程中,遇到了哪些挑战?花了多长时间?6、你之前的实习经历偏后端工程,你未来的职业规划更倾向于纯后端开发,还是希望从事与AI/大模型结合的工作?7、详细讲一下Golang中Channel的概念和作用,它是否是并发安全的?8、Channel和传统的锁(Mutex)在实现并发控制时有什么区别?各自的适用场景是什么?9、讲一下GMP模型10、当P的本地队列为空或者不为空时,它会怎么去调度G(协程)?11、Redis支持哪些数据结构12、为什么Redis的速度这么快13、如何实现一个类似淘宝搜索框的实时商品名称模糊搜索功能?14、实时输入联想与输入完成后点击搜索在技术实现上有什么本质区别?15、实时搜索通常使用什么网络协议(如WebSocket)?你了解或有使用过吗?讲一下16、请详细说明微信扫码登录的完整流程和背后发生的原理17、在微服务架构中,服务发现和负载均衡是如何实现的?18、服务注册中心(如Nacos,&nbsp;Consul)是如何工作的?服务实例如何注册和保活(如通过心跳机制)?19、讲一下Agent中的“长短期记忆”20、什么样的信息应该放在长期记忆,什么样的信息放在短期记忆?21、当对话轮数很多,上下文窗口不足时,有哪些处理策略?(如截断、压缩)22、如果要进行记忆压缩,通常有哪些方法?23、了解过Agent的设计范式吗?有哪些?24、你设计的Agent是怎么实现ReAct模式的?详细讲讲25、手撕:实现一个并发任务处理器:给定一个包含100个任务ID的列表,要求控制最大并发数为3,模拟并发调用某个外部接口(如打印ID)26、反问
三本咋了:很好的面筋
查看24道真题和解析
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

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