一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 575|回复: 6
收起左侧

[数组] candy的方法证明

[复制链接] |试试Instant~ |关注本帖
大成若缺 发表于 2016-2-10 23:50:58 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
https://leetcode.com/problems/candy/
candy这道题,要求ratings比邻居高的小朋友得到更多的糖果。ratings和邻居相等,则多少无所谓。每人至少一颗糖果,问最少需要多少糖果。
为什么遍历两遍的算法能保证结果是最小的,怎么证明?
stellari 发表于 2016-2-12 02:15:18 | 显示全部楼层
把所有小朋友的rating看做一条波形曲线,那么
1. 第一次从左向右遍历时,记录的Candy数其实是当前最大上升沿的长度;
2. 第二次从右向左遍历时,记录的Candy数其实是当前最大逆上升沿(从右向左看)的长度。
所以:
1. 在波谷处,左右两次遍历的结果必然都是1,因此波谷处小朋友得到的糖果一定是1。显然最优。
2. 在波峰处,假设左上升沿长度较大,那么波峰处小朋友得到的糖果如果小于左上升沿长度,那么左上升沿一侧一定会有至少两个小朋友无法分配;右侧同理。所以该算法得到的max(左上升沿长度,右下降沿长度)在波峰处也是最优。
3. 在非波峰波谷的上升沿处,采用的仅是第一次左->右遍历的结果,即左上升沿长度。同2,如果分配糖果数小于此值,那么左侧必然有两个小朋友无法分配。因此该值必定最优。
4. 在非波峰波谷的下降沿处,类似3,结果同样最优。
5. rating与左右都相等的情况,同1.

综合上述条件来看,在任何一点都不可能找到比该算法更优的结果,因此该算法(如果是正确的)结果必定最优。
回复 支持 1 反对 0

使用道具 举报

秋水有爱 发表于 2016-2-17 15:22:48 | 显示全部楼层
我也是西浦的可我等级不够不能加你好友,想问你最后去了哪所学校啊!
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-18 05:45:01 | 显示全部楼层
秋水有爱 发表于 2016-2-17 15:22
我也是西浦的可我等级不够不能加你好友,想问你最后去了哪所学校啊!

西浦是哪里?我没有去过,我是杭州的。
回复 支持 反对

使用道具 举报

秋水有爱 发表于 2016-2-18 15:30:44 | 显示全部楼层
大成若缺 发表于 2016-2-18 05:45
西浦是哪里?我没有去过,我是杭州的。

好吧,我看到你的一个帖子说你本科是xjtlu的...可能是我弄错了,不好意思啊...
不过你去SIT了吗?
回复 支持 反对

使用道具 举报

 楼主| 大成若缺 发表于 2016-2-19 12:10:51 | 显示全部楼层
秋水有爱 发表于 2016-2-18 15:30
好吧,我看到你的一个帖子说你本科是xjtlu的...可能是我弄错了,不好意思啊...
不过你去SIT了吗?

你又要再说一次不好意思了
你也可以再去一个随机的帖子下面问楼主,你去sit吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 22:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表