1.8小飞的调度算法

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

 

解法1：直接枚举暴力

 

解法2：时间可优化到O(n)

 

直觉反应，电梯在前面的状态对后面的状态有影响。粘带效应啊，很多题目都这样子~~

      红色代表停靠楼层，N1表示目的地在停靠楼层之下的人数，N2表示目的地在停靠楼层的人数，N3表示之上的人数。

 

设电梯在第i层停时，乘客走的总楼层数为x。若电梯在第i+1停靠时，乘客走的总楼层数为x'=x+N1+N2-N3  （低于的每人多走一层，高于的每人少走一层）

 

所以，要想总走楼层变少，只需保证y=N3-(N1+N2)>0，且y随着电梯的上升而减少，当y<0时，表示已经处在最佳楼层！

 

Code:

//初始化，第一层时
int n1=0;
int n2=1;
int n3=0;
int sum=0;
for(int i=2;i<=n;i++)
{
    n3+=np[i];   //np[]表示在第 i 层下电梯的人数
    sum+=np[i]*(i-1);
}

for(int i=2;i<=2;i++)
{
    if(n3>n1+n2)
    {
        sum+=n1+n2-n3;
        n1+=n2;      
        n2=np[i];
        n3-=np[i];    
    }
    else
        break;   //一旦不符合，将后都不可能符合
}