一道美团的笔试算法题

这道题目来源于我正在寻找实习机会的弟弟，他笔试的时候发挥不是很好，这道题目一直超时，就把题目拿过来问我有没有比较高效的做法。废话不多说，直接看题目吧

题目描述

有一款叫做空间回廊的游戏，游戏中有着n个房间依次相连，如图，1号房间可以走到2号房间，以此类推，n号房间可以走到1号房间。

这个游戏的最终目的是为了在这些房间中留下尽可能多的烙印，在每个房间里留下烙印所花费的法力值是不相同的，已知他共有m点法力值，这些法力是不可恢复的。

小明刚接触这款游戏，所以只会耿直的玩，所以他的每一个行动都是可以预料的：

1. 一开始小明位于1号房间。

2. 如果他剩余的法力能在当前的房间中留下一个烙印，那么他就会毫不犹豫的花费法力值。

3. 无论是否留下了烙印，下一个时刻他都会进入下一个房间，如果当前位于i房间，则会进入i+1房间，如果在n号房间则会进入1号房间。

4. 当重复经过某一个房间时，可以再次留下烙印。

很显然，这个游戏是会终止的，即剩余的法力值不能在任何房间留下烙印的时候，游戏终止。请问他共能留下多少个烙印。

输入要求

输入第一行有两个正整数n和m，分别代表房间数量和小明拥有的法力值。(1<=n<=100000,1<=m<=10^18)

输入第二行有n个正整数，分别代表1~n号房间留下烙印的法力值花费。(1<=a_i<=10^9)

输出要求

输出仅包含一个整数，即最多能留下的烙印。

算法效率要求

具体要求不太清楚，但是肯定是有限制的，因为我弟弟在做的时候一直超时。因此我们就尽可能的找出时间效率高的做法。

输入输出案例

# 输入
4 21
2 1 4 3

# 走过两圈，在每个房间各留下两个烙印后，跳过房间1，在房间2多留下一个烙印，因此输出为
9

输入输出不是算法题的精髓，我不打算去处理这个输入格式，直接简化一下题目：

编写一个函数 mark(energy, rooms)，energy 为小明拥有的法力值，rooms 为房间队列，每个元素代表一个房间，值为房间留下烙印所需要消耗的法力值，函数输出小明最终能留下的烙印数。

解析

首先我们不考虑时间与空间的复杂度，最直观、最简单的算法，就是老老实实绕着这个圈一个一个的走房间，直到一整圈下来没有留下烙印或者法力值已经用完。实现起来非常简单：

// 算法 v1.0
function mark (energy, rooms) {
  let result = 0
  let marked, i
  const n = rooms.length
  while (true) {
    marked = 0
    for (i = 0; i < n; i++) {
      if (energy >= rooms[i]) {
        result++
        marked = 1
        energy -= rooms[i]
      }
    }
    if (!marked || energy === 0) {
      break
    }
  }
  return result
}

上面就是最基础的 v1.0 版本的算法了，很明显，这个算法效率非常一般，在大数据量下必然会超时，我们在这个基础上，一步步的提高算法效率。

这时候问题就来了，优化思路从哪里来？其实做算法题时，有一个很简单但很有用的思考角度，我们可以拟定一些特殊的输入数据，从特殊的输入数据入手：

法力值 energy 非常大

最容易想到的特殊输入情况就是这个，如果按照算法 v1.0 ，拥有非常大的法力值时，循环次数就会非常大，耗时自然也会很大。那么有没有方法简化？当然有。

观察一下题目和程序，我们很容易发现，在法力值很大时，前面有很多圈留下的烙印数其实是一样的，可以通过数学求值，并不需要真的进入循环：

// 算法 v2.0
function mark (energy, rooms) {
  let result = 0
  let marked, i
  const n = rooms.length
  let sum = 0
  for (i = 0; i < n; i++) {
    sum += rooms[i]
  }
  if (energy >= sum) {
    result += n * parseInt(energy / sum)
    energy %= sum
  }
  while (true) {
    marked = 0
    for (i = 0; i < n; i++) {
      if (energy >= rooms[i]) {
        result++
        marked = 1
        energy -= rooms[i]
      }
    }
    if (!marked || energy === 0) {
      break
    }
  }
  return result
}

根据上面这个算法，在法力值很大的情况下，通过计算完整一圈的法力消耗值和取模，可以减少很多圈不必要的循环，效率自然也就提高了不少。

但是，这样就够了吗？

我们再从另一个特殊的输入数据来看：

小明法力值为 100 万，房间数量为 1 万，其中 9999 个房间所需法力值为 1000001，剩下的 1 个房间所需法力值为 1

那么，我们仍然需要为这一个房间跑 100 万次回廊，这显然是不能接受的。我们来看看这种情况如何优化

房间法力值相差很大

当房间法力值相差很大时，我们可以注意到，其实大部分所需法力值比较大的房间在比较后面的循环中根本不需要考虑，因为它已经超过了当前法力值，每一圈之后，一圈消耗的法力值都有可能变更。很显然，我们可以改进一下算法，每一圈都计算新的 sum 值，并对剩余法力值取模：

// 算法 v3.0
function mark (energy, rooms) {
  let result = 0
  let i, marked, sum, lastResult
  while (true) {
    // 重置变量
    marked = false
    sum = 0
    lastResult = result
    for (i = 0; i < rooms.length; i++) {
      if (energy >= rooms[i]) {
        result++
        marked = true           // 标记一圈下来是否有留下烙印
        sum += rooms[i]         // 计算一圈下来消耗的总法力值
        energy -= rooms[i]
      }
    }
    // 每一圈后根据消耗法力值对剩余法力值取模并更新烙印数
    if (energy >= sum) {
      result += (result - lastResult) * parseInt(energy / sum)
      energy %= sum
    }
    // 当一圈下来没有房间留下烙印或法力值为空，则游戏结束
    if (!marked || energy === 0) {
      break
    }
  }
  return result
}

到这里，这个算法其实已经有点样子了，大部分情况下都可以表现的不错，那还有没有可以优化的地方？答案是有的，当然这个地方不是很容易想到。

压缩数据

思考一个点，在回廊中行走时，我们真的有必要每个房间都走吗？其实并不需要，事实上，在上一轮走回廊的过程中，我们已经知道了哪些房间已经超过当前剩余法力值，完全可以将其剔除。因此，我们可以维护一个新的房间列表，来储存实际上需要进入的那些房间，这样，房间列表的长度会越来越小，效率自然也就越来越高。

// 算法 v4.0
function mark(energy, rooms) {
  let result = 0
  let i, j, marked, sum, lastResult
  while (true) {
    // 重置变量
    marked = false
    i = 0
    j = 0
    sum = 0
    lastResult = result
    for (j = 0; j < rooms.length; j++) {
      if (energy >= rooms[j]) {
        result++
        marked = true           // 标记一圈下来是否有留下烙印
        sum += rooms[j]         // 计算一圈下来消耗的总法力值
        energy -= rooms[j]
        rooms[i++] = rooms[j]
      }
    }
    // 每一圈后
    // 1. 根据消耗法力值对剩余法力值取模并更新烙印数
    // 2. 更新房间长度
    if (energy >= sum) {
      result += (result - lastResult) * parseInt(energy / sum)
      energy %= sum
      rooms.length = i
    }
    // 当一圈下来没有房间留下烙印或法力值为空，则游戏结束
    if (!marked || energy === 0) {
      break
    }
  }
  return result
}

现在算法看起来就很完美了，那还有没有优化的地方？

没有了，我真的一滴都不剩了（污

最后

算法很多人第一印象就是难，尤其是前端同学，闻算法色变，但是算法是很重要的，从算法、编译原理、计算机网络到编译原理等基础知识，决定了你在技术这条路上的上限，还是需要好好学习的。算法难归难，用心去学习整理，还是有规律可循的。

关于这道题目的完整思路就是这些了，如果你对于上面的解法有新的想法或者你有更好的解决方案，欢迎评论区留下你的见解。