编程之美：小飞的电梯调度算法

本文主要是介绍编程之美：小飞的电梯调度算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

有一部电梯，有n个人要上楼，但是电梯只在一层停，所以难免有人出电梯后要下楼或者上楼，求电梯在那层停可使所有乘客所爬楼层最少？

分析：

1、枚举法，时间复杂度O(n^2)

2、假设电梯停在第i层，算出所哟乘客共要爬楼的层数是Y，如果有N1个乘客目的楼层在i层以下，有N2个乘客正好在i层，有N3个乘客在i层以上。如果电梯改在第i-1层停，就有所有目的地在i层及以上的乘客都需多爬一层，即多爬N2+N3层；所有目的地在i层以下的乘客需少爬一层，即少爬N1层，因此乘客共需爬的层数是Y-N1+(N2+N3)

同理，如果改在i+1层停，乘客共需爬楼Y+(N1+N2-N3)层

由此，当N1>N2+N3时，电梯停在i-1层更好，当N1+N2<N3时，电梯停在i+1层更好，其他情况停在i层更好

#include <iostream>
#include <algorithm>
using namespace std;const int N=10;//总共10层楼int person[N+1]={0,0,2,1,3,4,0,5,3,0,0};//到第i层的乘客数
int target;//电梯停靠楼层int main(){int N1=0,N2=0,N3=0;int floor=0;N2=person[1];for(int i=2;i<=N;i++){N3+=person[i];floor+=person[i]*(i-1);}target=1;for(int i=2;i<=N;i++){if(N1+N2<N3){target=i;floor += (N1+N2-N3);N1 += N2;N2 = person[i];N3 -= person[i];}else break;}cout<<"电梯停在"<<target<<"层"<<endl<<"乘客需爬楼"<<floor<<"层"<<endl;return 0;
}

这篇关于编程之美：小飞的电梯调度算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---