电梯在高峰时间，每层都有人上下，电梯每层都停，在繁忙的上下班时间，每次电梯从一层往上走时，假设只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。
问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？
原始解法
初始数组设定每层楼的人数，遍历所有楼层，统计最佳爬楼梯的层数最少,时间复杂度O(n²).
<pre><code>` func compute(person:[Int],maxFloor:Int) -> (Int,Int) {
var minFloor:Int = 0
var targetFloor:Int = 0
for i in 1...maxFloor { // 电梯停留在i层
var temp:Int = 0
for j in 1...maxFloor {
temp += person[j] * abs(i - j)
}
if i == 1 {
minFloor = temp
targetFloor = 1
} else {
if temp < minFloor {
minFloor = temp
targetFloor = i
}
}
}
return (minFloor,targetFloor)
}
`</code></pre>
最简单解法
假设N1为第i层以下的乘客数，N2为第i层的乘客数，N3为第i层以上的乘客数，已知乘客在第i层的nFloor值为count
如果电梯改停在i-1层时，那么此时nFloor值为count-N1+（N2+N3）
如果电梯改停在i+1层时，此时nFloor值为count+N1+N2-N3
由此可见N1+N2<N3时，停i+1层更好，这样我们先计算第一层时的N1、N2、N3的值，时间复杂度为O(n).
<pre><code>` func compute2(person:[Int],maxFloor:Int) -> (Int,Int) {
var n1:Int = 0 // 第i层以下的人数
var n2:Int = person[1] // 第i层的人数
var n3:Int = 0 // 第i层以上的人数
var countFloor:Int = 0 // 第i层的时候所走的楼层总数
var targetFloor:Int = 1
for i in 2...maxFloor {
countFloor += person[i] * (i - 1)
n3 += person[i]
}
// 如果楼层变为i-1层 总层为 count + (n2 + n3 - n1)
// 如果楼层变为i+1层 总层为 count + (n1 + n2 - n3)
for i in 2...maxFloor {
if n1+n2 < n3 {
targetFloor = i
countFloor += n1 + n2 - n3
n1 += n2 //n1 增加
n2 = person[i]
n3 -= person[i] // n3 减少
} else {
break
}
}
return (countFloor,targetFloor)
}`</code></pre>
测试代码:
<pre><code>`var personFloor:[Int] = [0 ,2 , 3, 5, 10, 8, 6]
var elevator:Elevator = Elevator()
var result = elevator.compute(person: personFloor, maxFloor: 6)
print("FlyElephant-走的最小的路层--(result.0)--最佳楼层---(result.1)")
var result2 = elevator.compute2(person: personFloor, maxFloor: 6)
print("FlyElephant-走的最小的路层--(result2.0)--最佳楼层---(result2.1)")`</code></pre>
