找回密码
 立即注册

QQ登录

只需一步,快速开始

搜索

[ 智力面试题 ] [守望者 智力面试题]孩子分糖果

2014-09-23 12:05| 发布者: watchmen | 查看: 1455 | 收藏

摘要: N个孩子站成一排,每个人分给一个权重。按照如下的规则分配糖果:1. 每个孩子至少有一个糖果2. 所分配权重较高的孩子,会比他的邻居获得更多的糖果问题是,最少需要多少个糖果? ... ...
N个孩子站成一排,每个人分给一个权重。
按照如下的规则分配糖果:
1. 每个孩子至少有一个糖果
2. 所分配权重较高的孩子,会比他的邻居获得更多的糖果
问题是,最少需要多少个糖果?

你有新的观点?  

已有1参与讨论

  • 参考思路:

    这个题目是要求找到最少需要多少个糖果。最少的糖果是存在的,体现在哪里呢?权重较高的孩子,会比他的邻居们获得更多的糖果,那么多多少呢?可以是 1个,2个,或者更多个,但显然,当多一个的时候。总的糖果的数量是最少的,除此之外呢?当某一个孩子的邻居的权重都比他大,那他应该获得多少个糖果呢? 只有一个——每个孩子至少要得到一个。

    所以根据上面的分析,我们可以想办法找到权重数组A中的波谷(也就是权重小于邻居们的孩子),很显然这些孩子每人只可以分得一个糖果。我们开辟一个 新的数组B,表示每个孩子可以得到的最少的糖果数。扫描一遍A,得到所有的波谷的孩子,然后将对应的B的值设置为1.对于第一个和最后一个权重,只要 A[0]

    然后该如何确定其他孩子的糖果数呢?我们看一个具体的例子,来更加形象的说明如何求得。如下表:

    A        1        2        3        4        2        6
    B        1                                1       
    现在已经确定B中两个孩子的最少糖果数,然后:

    1. B[0]=1,那么B[1]=2,B[2]=3,B[3]=4,是一定的。原因是要满足题目中的第2个条件。

    2. 同理,B[5]=2。

    3. 上面的是按照数据的正向看的,如果逆向,则B[3]=2,因为B[4]=1。这时,出现了冲突,要满足最少的糖果数,似乎要取B[3]=2,但是不满足条件2.所以遇到这个情况,则选取较大的。得到表格如下:
    A        1        2        3        4        2        6
    B        1        2        3        4        1        2
    则最少糖果数为(1+2+3+4+1+2) = 13个。

    总结算法步骤如下:

    1. 找到数组的波谷,将波谷的孩子的糖果数设置为1.此步:时间复杂度O(n),空间复杂度O(n)

    2. 从左到右遍历数组,从每一个1开始,其后的孩子的糖果比前一个孩子多1个,直到波峰。此步:时间复杂度O(n)

    3. 从右向左遍历数组,从每一个1开始,其后的孩子的糖果比前一个孩子多1个。波峰的孩子,与2步中的相比,取最大的糖果个数。

    4. B数组每一个元素求和,即可得到最少需要的糖果数。
    整体算法的时间复杂度为O(n),空间复杂度为O(n)。进一步优化,可以将找波谷的一次循环省略。
    zhouy

    2014-10-17 14:57

赞过此文的人

推荐阅读

[守望者 内推职位]中电科网络信息安全有限责任公司
[守望者 内推职位]中电科网络信息安全
中国电子科技集团公司第三十研究所(以下简称:三十所)创建于1965年,是集通
[守望者 猎头职位] 某民机航电公司  研发技术副总监 VxWorks软件高级工程师 Linux软件 ...
[守望者 猎头职位] 某民机航电公司 研
以下职位为猎头职位。有兴趣可将简历发送到362528717@qq.com或者加QQ交流,匹
[猎头职位] 高级嵌入式系统架构师
[猎头职位] 高级嵌入式系统架构师
高级嵌入式系统架构师
[猎头职位] 英国金融公司 liquid(利源软件)Linux C++高级开发
[猎头职位] 英国金融公司 liquid(利源
Liquid Capital Group 是一家总部位于伦敦的专门从事金融衍生品交易和做市业
[猎头职位] 系统测试__安全产品测试
[猎头职位] 系统测试__安全产品测试
系统测试__安全产品测试
【守望者 内推职位】腾讯平台架构后台开发工程师
【守望者 内推职位】腾讯平台架构后台
守望者:腾讯后端开发,职位在深圳,年薪30~35W,成都主要为游戏开发相关职位
[猎头职位] 加拿大 宏利金融  .Net 高级开发
[猎头职位] 加拿大 宏利金融 .Net 高
守望者:本职位为金融开发相关陪伴,要求有较强的架构设计能力,开发能力,分
[内部推荐]重庆金鑫智慧java高级程序员
[内部推荐]重庆金鑫智慧java高级程序员
守望者:重庆金鑫智慧是重庆南桐矿业集团公司旗下的子公司,有专业的队伍进行
【猎头职位】欧美软件开发公司  ASP.NET高级工程师
【猎头职位】欧美软件开发公司 ASP.NE
公司专门对欧美软件外包服务提供商。公司在多个领域有着独到和突出的技术,包
[猎头职位] windows客户端开发工程师或leader 公共技术客户端高级架构师(深圳) ... .. ...
[猎头职位] windows客户端开发工程师或
守望者:以下两个职位为互动娱乐高端管理职位。主要工作为游戏开发及项目管理
【守望者  面试交流】HR谈 如何使用E-mail投递简历
【守望者 面试交流】HR谈 如何使用E-m
守望者:现在的简历一般都使用E-mail发送,然而,随着信息泛滥,HR需要从浩瀚

行业聚焦  面试交流  职位推荐  开发视频   技术交流  腾讯微博  新浪微博

友情链接:课课家教育  阿里云  鲜果  W3Cfuns前端网  中国企业家  环球企业家  投资界  传媒梦工场  MSN中文网  Android开发者社区  cnbeta  投资中国网  又拍云存储  美通说传播  IT茶馆  网商在线  商业评论网  TechOrange  IT时代周刊  3W创新传媒  开源中国社区  二维工坊  Iconfans  推酷  智能电视网  FreeBuf黑客与极客  财经网  DoNews  凤凰财经  新财富  eoe移动开发者社区  i黑马  网易科技  新浪科技  搜狐IT  创业家  创业邦  腾讯财经  福布斯中文网  天下网商  TechWeb  雷锋网  新浪创业  和讯科技  品途O2O  极客公园  艾瑞网  抽屉新热榜  卖家网  人民网通信频道  拉勾网  创新派  简单云主机  

手机版|黑名单|守望者在线 在线教育 linux 高级程序设计 C/C++ 大数据 ( 蜀ICP备14029946号

成都守望者科技有限公司 © 2013-2016 All Rights Reserved