QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 27105|回复: 51
打印 上一主题 下一主题

[问题求助] 两个算法问题

[复制链接]
字体大小: 正常 放大

7

主题

3

听众

154

积分

升级  27%

  • TA的每日心情
    难过
    2012-4-27 07:46
  • 签到天数: 4 天

    [LV.2]偶尔看看I

    自我介绍
    爱好数学,计算机编程,下象棋

    群组华中科技大学

    跳转到指定楼层
    #
    发表于 2010-9-9 19:28 |只看该作者 |正序浏览
    |招呼Ta 关注Ta
    1.Google面试题,求kth largest element


    you are given 2 arrays sorted in decreasing order of size m and n  
    respectively.

    Input: a number k <= n*m and >= 1

    Output: the kth largest sum(a+b) possible. where
    a (any element from array 1)
    b (any element from array 2)

    两个数组A,B 求第k个sum(a+b)。

    如果直接一个一个算的话,从大到小,需要O(k)复杂度。
    有没有O(logk)或者O(1)的方法。


    2.排列与统筹学结合的经典问题


    问题:
    设方程组(如下)有解:
    X1+3+X12=X2
    X2+4+X13=X3
    X2+4+X14=X4
    X3+5+X15=X5
    X4+7+X16=X5
    X5+8+X17=X6
    X6+1+X18=48
    X7+5+X19=X8
    X8+1+X20=X9
    X8+1+X21=X10
    X10+2+X22=29
    X9+9+X23=X11
    X11+7+X24=29
    (Xi≥0;i =1,2,…24)

    集合:
    A={X1,X3,X5,X7,X8,X10,X11};
    B={X2,X4,X6,X9};

    设A中元素组成m组排列,B中元素组成n组排列.
    每个集合中的元素取且仅取一次.(如A中可以形成3组排列:X3X8X7,X1,X5X10X11)
    每个排列中元素按照排列顺序满足条件:
    Xi+Txi≤Xj (j为排在i后元素,Txi为Xi所在上述方程式左侧时,该方程式中的常量,如Tx2=4)

    (如:排列X1X3X7,满足条件
    X1+3≤X3
    X3+5≤X7 )


    求满足方程组时,m+n最小时的排列.



    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    peter1977        

    10

    主题

    1

    听众

    141

    积分

    升级  20.5%

  • TA的每日心情

    2018-7-12 00:40
  • 签到天数: 34 天

    [LV.5]常住居民I

    自我介绍
    不拘小节,不亏大义
    回复

    使用道具 举报

    540136593        

    0

    主题

    1

    听众

    1

    积分

    升级  20%

    该用户从未签到

    回复

    使用道具 举报

    LYJA        

    20

    主题

    3

    听众

    375

    积分

    升级  25%

  • TA的每日心情
    开心
    2017-8-27 23:29
  • 签到天数: 61 天

    [LV.6]常住居民II

    社区QQ达人

    回复

    使用道具 举报

    3

    主题

    6

    听众

    471

    积分

    升级  57%

  • TA的每日心情
    无聊
    2014-9-10 22:13
  • 签到天数: 13 天

    [LV.3]偶尔看看II

    自我介绍
    喜欢matlab

    群组第一期sas基础实训课堂

    群组数学建模培训课堂1

    群组2014年地区赛数学建模

    群组数学中国第二期SAS培训

    群组数模专题强化培训

    回复

    使用道具 举报

    0

    主题

    16

    听众

    666

    积分

    升级  16.5%

  • TA的每日心情
    无聊
    2018-8-4 15:30
  • 签到天数: 77 天

    [LV.6]常住居民II

    自我介绍
    爱数学

    群组数模专题强化培训

    群组2014年地区赛数学建模

    群组国赛讨论

    群组第二届数模基础实训

    回复

    使用道具 举报

    499379348        

    0

    主题

    10

    听众

    16

    积分

    升级  11.58%

  • TA的每日心情

    2014-8-1 17:02
  • 签到天数: 3 天

    [LV.2]偶尔看看I

    自我介绍
    For What?
    回复

    使用道具 举报

    1221long        

    0

    主题

    0

    听众

    3

    积分

    升级  60%

    该用户从未签到

    自我介绍
    思考者
    回复

    使用道具 举报

    8

    主题

    4

    听众

    353

    积分

    升级  17.67%

  • TA的每日心情
    郁闷
    2012-5-5 09:53
  • 签到天数: 22 天

    [LV.4]偶尔看看III

    回复

    使用道具 举报

    0

    主题

    4

    听众

    744

    积分

    升级  36%

  • TA的每日心情
    无聊
    2012-2-23 09:12
  • 签到天数: 108 天

    [LV.6]常住居民II

    回复

    使用道具 举报

    chenxs008        

    4

    主题

    3

    听众

    23

    积分

    升级  18.95%

  • TA的每日心情
    奋斗
    2013-9-14 12:07
  • 签到天数: 1 天

    [LV.1]初来乍到

    新人进步奖

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2025-7-10 10:19 , Processed in 0.990650 second(s), 114 queries .

    回顶部