2019-07-31.md

每日一题 - 小飞电梯调度问题

信息卡片

• 时间： 2019-07-31
• 题目链接：暂无
• tag：Math Dynamic Programming

题目描述：

微软亚洲研究所所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯在每层都停。实习生小飞常常会被每层都停的电梯弄得很不耐烦，于是他提出了这样一个办法：
由于楼层并不太高看没在繁忙的上下班时间，每层电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有的乘客都从一楼上电梯，到达某层楼后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。
在一楼的时候，每个乘客选择自己的目的层，电梯则自动计算出应停的楼层。
问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。

扩展：

1.如何在O(n)的时间复杂度完成？
2.往上爬楼梯，总是比往下走要累的。假设往上爬一个楼层，要耗费k单位的能量，而往下走只需要耗费1单位的能量，那么如果题目条件改为让所有人消耗的能量最少，这个问题怎么解决呢？
这个问题可以用类似上面的分析方法来解答看，因此笔者不再累述，留给读者自行解决。
3.在一个高楼里面，电梯只在某一个楼层停，这个政策还是不太人性化。如果电梯会在k个楼层停呢？读者可以发挥自己的想象力，看看如何寻找最优方案。

参考答案

题意是 每层都停 => 只停一层，其余让人爬楼梯；所有人爬梯之和最小 选择目的层(i)，在i层下的人数是T[i]，根据大家选择的目的层计算在哪一层(X)停最优 sum(1～N){T[i]*|i-x|}的最小值

从简单易想到的方式开始； 从1楼开始直到顶层，算出在每层人需要爬梯的总和数组result 找出Min(result)下标 时间复杂度是O(N^2)

/**
* 两个测试数据
* nPerson = [0, 1, 3, 4, 2, 3]
* nPerson = [0, 1, 0, 2, 2, 6]
*/
function original(nPerson) { // nPerson首元素设0，使楼层与下标对应
  // nPerson[i] 在i层下的人， N 总楼层
  let result = [0]; // 存各层结果
  let target = 1; // 最小值下标
  for(let x = 1; x < nPerson.length; x++) { // 目标楼层x
    result[x]=0;
    for(let i = 1; i < nPerson.length; i++) { // 人在哪层停留
      result[x] += nPerson[i]*Math.abs(x-i);
    }
    if(result[target] > result[x]) {
      target = x
    }
  }
  return target;
}

进一步考虑(动态规划) 假设在i层停，共需要爬Y阶；在i层有N2人，在i层以下共N1人，i层以上共N3人
如果在i-1层停，相比i层变化Y+N2+N3-N1 = Y - (N1-N2-N3) => N1 > (N2 + N3)时会减少爬阶数
如果在i+1层停，相比i层变化Y-N3+N2+N1 = Y - (N3-N2-N1) => N3 > (N2 + N1)时会减少爬阶数
所以在N1 > N2+N3时应该在i-1层停，N3 > N2+N1时应该在i+1层停; 否则在i层停

初始状态电梯停在第一层，向上进行状态的变迁，开始时N2 + N1 - N3 < 0
sum越来越小，直到某一层N2 + N1 >= N3，就没有必要在往上走了。这时已求出最合适的楼层了

function betterOne(nPerson) { // 首元素设空, 下标就与楼层对应了，nPerson的长度-1就是楼层数
    let N1 = 0;
    let N2 = nPerson[1];
    let N3 = 0;
    let target = 1;
    // 第一层时，算出人需要走的楼梯数Y和在一楼以上的人数N3
    for(let i = 2; i < nPerson.length; i++) {
        N3 += nPerson[i];
    }
    // 再来优化
    for(let i = 2; i < nPerson.length; i++) {
        if (N1+N2 < N3) { // 在i+1层停较优
            target = i;
            N1 += N2
            N3 -= nPerson[i]
            N2 = nPerson[i]
        } else {
            break
        }
    }
    return target
}

扩展问题2的解 向上爬比向下走更耗费体力，假设上楼是下楼耗费能量的k倍；k大于1
比较消耗能量的大小决定楼层，只需在动态规划方式上增加权重即可

function betterOnewithWeight(nPerson, k) { // 首元素设空, 下标就与楼层对应了，nPerson的长度-1就是楼层数
    let N1 = 0;
    let N2 = nPerson[1];
    let N3 = 0;
    let target = 1;
    // 第一层时，算出人需要走的楼梯数Y和在一楼以上的人数N3
    for(let i = 2; i < nPerson.length; i++) {
        N3 += nPerson[i];
    }
    // 再来优化
    for(let i = 2; i < nPerson.length; i++) {
        if (N1+N2 < N3*k) { // 在i+1层停比较好
            target = i;
            N1 += N2
            N3 -= nPerson[i]
            N2 = nPerson[i]
        } else {
            break;
        }
    }
    return target
}

其他优秀解答

中位数方法

假设两个人在2楼和9楼下。那么在2-9楼之间任意层停，两人走楼梯的层数和是不变的
换一组(第二小、第二大)人也是这么处理
将每个人要去的楼层从低到高逐一排列，找到中位数，此中位数就是最优楼层

时间复杂度O(N)

/**
* 中位数方法
*/
function median(nPerson) {
    const newArr = []; // 存楼层
    for(let i=0; i < nPerson.length; i++) {
      while(nPerson[i] > 0) {
        newArr.push(i)
        nPerson[i]--
      }
    }
    let len = newArr.length;
    // 返回楼层中位数
    return len % 2 == 1 ? newArr[(len+1)/2] : newArr[len/2]
}