电梯调度算法
题目描述
大厦中有电梯，在高峰时间，每层都有人上下，电梯在每层都停。
想的解决办法如下：
所有的乘客都从一楼上电梯，每个乘客选择自己的目的层，之后电梯自动计算出一个楼层。
电梯往上走时，只在这个楼层停下来，所有的乘客再从这里爬楼梯到自己的目的楼层。
现在就想问，电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少。
分析
该问题本质上是一个优化问题。
首先为这个问题找到一个合适的抽象模型。
有两个因素会影响结果：乘客的数目和乘客的目的楼层。
假设楼层总共有N层，电梯停在x层，要去第i层的乘客数目总数为Tot[i]，这样，所爬楼梯的总数就是:
因此，我们就是需要找到一个整数x，使得上式的值最小。
解法一
最为直接的一个解法就是从第一层开始，枚举x一直到第N层，计算出电梯在第x层楼停的话，所有乘客总共需要爬多少楼。
这个算法需要两重循环来完成。
代码如下：
解法一 #includeusing namespace std;int main(int argc, char* argv[]){ int N = 0; int nPerson[100]; int nFloor, nMinFloor, nTargetFloor; nTargetFloor = -1; while( cin >> N) //输入总的楼层 { //进行状态清零 nTargetFloor = -1; nMinFloor = 0; //输入到每一层的人的个数 for(int i = 0; i < N; ++i) { cin >> nPerson[i]; } //开始计算最佳楼层 for(int i = 0; i < N; ++i) { //对于每一个楼层，先假设是停在这个楼层 //用一个变量记录要步行的楼层总数 nFloor = 0; //假设停在第i层，统计所有人需要步行的楼层总数 for(int j = 0; j < N; ++j) { if(j < i) { nFloor += nPerson[j] * (i - j); } else if(j > i) { nFloor += nPerson[j] + (j - i); } } //第一次记录，或者当前结果小于之前最小时，记录结果 if(-1 == nTargetFloor || nMinFloor > nFloor) { nMinFloor = nFloor; nTargetFloor = i; } } //输出计算结果 cout << "The best floor is: " << nTargetFloor + 1 << endl; } return 0;}
这个基本解法的时间复杂度为O(N2)。
解法二
假设电梯停在i层，我们可以计算出所有乘客总共需要爬楼梯的层数Y。
假设有N1个乘客在i层楼以下，N2个乘客在第i层楼，还有N3个乘客在第i层楼以上。
这个时候，如果电梯改停在i-1层，所有目的地在第i层及以上的乘客都需要多爬一层，即N2+N3层，而所有目的地在i-1层及以下的乘客可以少爬一层，总共可以少爬N1层。
因此，乘客总共需要爬的层数为Y-N1+N2+N3 = Y-(N1-N2-N3)层。
反之，如果电梯在i+1层停，则总共需要爬的层数为Y+(N1+N2-N3)层。
由此可见：
当N1 > N2 + N3时，i-1层比i层好；
当N1 + N2 < N3时，i+1层比i层好。
根据这个规律，我们从第一层开始考察，计算各位乘客需要爬楼梯的层数。然后再根据上面的策略进行调整，直到找到最佳楼层。
解法二 #includeusing namespace std;int main(int argc, char* argv[]){ int N = 0; int nPerson[100]; int nMinFloor, nTargetFloor; int N1, N2, N3; while( cin >> N) //输入总的楼层 { //输入到每一层的人的个数 for(int i = 0; i < N; ++i) { cin >> nPerson[i]; } //进行状态清零 nTargetFloor = 0; nMinFloor = 0; N1 = 0; N2 = nPerson[0]; N3 = 0; for (int i = 1; i < N; ++i) { N3 += nPerson[i]; nMinFloor += nPerson[i] * (i - 1); } for(int i = 1; i < N; ++i) { if(N1 + N2 < N3) { nTargetFloor = i; nMinFloor +=(N1 + N2 - N3); N1 += N2; N2 = nPerson[i]; N3 -= N2; } else { //否则第i层的结果已经最小，故不需要计算第i+1层 break; } } //输出计算结果 cout << "The best floor is: " << nTargetFloor + 1 << endl; } return 0;}
总的时间复杂度将降为O(N)。
参考资料
《编程之美》1.8节
相关博客：
PS:
每天更新有点扛不住了，还是不要强求每天了。。。