一个酒吧内有排成一行的25个座位,到酒吧的客人都生性内向不擅交际,因此他们都会坐到离其他人最远的位置(即离最近的人最远),如果新进来的客人发现左右两边都有人没有空位的话就会离开。你做为老板希望客人越多越好,如果你可以安排第一个进来的客人坐什么地方,该怎么安排?

3 4 收藏


直接登录
最新评论
  • yamade   2016/01/02

    安排在八分之一处吗?

  • sdkl   2016/01/02

    坐边上

  • qzuser   2016/01/02

    偶数随便挑一个

  • 撞风   2016/01/02

    坐在第9或第17号位

  • yinwoods   2016/01/03

    1+3X的位置,因为划分为小问题来看,我们最后想要的是每个坐人的座位中间空出两个座位。

  • babyggyy   2016/01/03

    奇数位随便一个

  • tianxun   2016/01/03

    等答案。。。

    • bt   2016/01/04

      将问题缩小一些,比方说有5个,这个时候画一下就能理解了 -。- 应该是奇数位就可以

  • 端点星 一介码农 2016/01/03

    最终客人都会坐成两边相隔,所以客人最多的情况是奇数位坐满,安排在奇数位就可以。

  • . 学生,未来的码农 2016/01/03

    “左右两边都有人没有空位”意思是可以有一边有人?,那样的话放在正中间就能达到两人一空两人一空的最多情况,但是不会这么简单吧。
    如果是要求左右两边都没人,那么是九或十七,因为人数最多的情况是隔一个坐一个,反过来逆推一下就能得出。

  • 第十三个,这样就能最后把最小单位划分为四个,而长度为四的可以坐三个人,应该是效率最高的

  • 袁言 工程师 2016/01/03

    binary code: make sure half part is all 1: xxxxx, so: 9 or 17th is fine

    • 1989aa   2016/01/05

      9跟17 确实是最优解,但是我是从1 3 5 9 17这样递推的,请问用二进制的思路是怎样的?

  • divinites Assistant Prof. 2016/01/04

    2号或者24号,因为最终应该是每隔两个人空一个位子。

  • Champ 硕士在读 2016/01/04

    这个应该动态规划求解,每个空格长度对应一个状态,包含4种情况,分别是两端座位是否有人。

  • hstdt   2016/01/04

    除了7 11 15 19以外的奇数吧.

    即所有4x+1的位置和小于等于5的奇数(即3),大于等于21的奇数(即23)

    比如如果在7,那么1001001,左边会被分割成这样(1代表有人),不符合要求

    如果是27,可能答案就不是上面这个规律了

  • hstdt   2016/01/04

    除了7 11 15 19以外的奇数吧.

    即所有4x+1的位置和小于等于5的奇数(即3),大于等于21的奇数(即23)

    比如如果在7,那么1001001,左边会被分割成这样(1代表有人),不符合要求

    如果是27,可能答案就不是上面这个规律了

    PS:上面是从左往右数要符合的规律,从右往左数也要符合这个规律,而题目为25,那么7对应19,11对应15.

  • 苍森弭海   2016/01/05

    1,4,7,10,13,16,19,22,25只要在这些号码里面任选一个作为第一人,就可以满足条件的达到最多客人数量

  • 1989aa   2016/01/05

    分析得头头世道,都不知道试一试么。譬如从1开始,得到了 1>25>13>7>4 1 4之间两个空格,并不是最优解。最优解只有9跟17.反推即可。1>3>5>9>17。

  • vanishfan   2016/01/06

    9或17处。
    若要最多人,则必须是1.3.5…25这些位置占据了才行,其他方式都不是最多人的。因为每次找座位都是在所有间隔大于等于3的空隙里找中间点,故要让中间点正好都为奇数点,那么第一个位置确认后,后续间隔需为2的n次方,即1-9之间有4个最小空隙,9-25之间有8个最小空隙。

  • 王先生 学生 2016/01/06

    因为25是奇数,所以仅考虑奇数情况,设座位数为N
    情况分两种:
    1.N/4 余1. 直接安排在左边第一个位置或右边第一个即可,
    随后进来的人会坐在坐位区间的中点处,以此类推。
    本题就是这种情况,最多13位顾客。
    2.N/4 余3. 如像情况一那样安排,则在占据首尾,中间的位置后,
    剩余坐位是偶数,无法达到最优解,例如N=7:
    人空空人空空人
    故不能简单安排在首尾的位置上,正确方法是在中间找个位置,
    可能性有很多种,
    遵循的原则是分割后两个有人坐位中间剩余位置是奇数,
    这样又回到二分的那种情况愉快的进行下去达到最优解:
    人空人空人空人空。。。人空人空人

    • JasonTian 学生 2016/01/11

      题目中说的是两边“都”有人,新顾客才会离开,所以 人人空人人空人人空。。。 是不是更好一些呢,第一个顾客放在中间的话能做17个。

  • EternalStop 运维工程师 2016/01/06

    不是2+3X的位置就可以了,对吗?

  • 扳转在手 Ingénieur 2016/01/06

    没有确定的最终情况,对于奇数个座位,安排在任意1+3X上,中间态必达1001001001…1,其他则是动态的,不过最终达到每四个座位坐3个,是老板最想要的,举例:101110111…1,中间111是可能达成的,并不违背题意“新客人”

  • 你就是_   2016/01/15

    9或者17。