牛牛的揠苗助长

牛牛的揠苗助长

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数组中位数时取到最小值。

全部评论

相关推荐

11-24 00:11
已编辑
广东工业大学 算法工程师
避雷深圳&nbsp;&nbsp;yidao,试用期&nbsp;6&nbsp;个月。好嘛,试用期还没结束,就直接告诉你尽快找下一家吧,我谢谢您嘞
牛客75408465号:笑死,直属领导和 hr 口径都没统一,各自说了一些离谱的被裁理由,你们能不能认真一点呀,哈哈哈哈哈😅😅😅
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:52
点赞 评论 收藏
分享
粗心的雪碧不放弃:纯学历问题,我这几个月也是一直优化自己的简历,后来发现优化到我自己都觉得牛逼的时候,发现面试数量也没有提升,真就纯学历问题
点赞 评论 收藏
分享
3 收藏 评论
分享
牛客网
牛客企业服务