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

//O(N^2)
void f(int nPerson[],int N,int &nMinFloor,int &nTargetFloor)
{
    nMinFloor=INT_MAX;
    nTargetFloor=0;
for(int i=1;i<=N;++i)
    {
int nFloor=0;
for(int j=1;j<i;++j)nFloor+=nPerson[j]*(i-j);
for(int j=i+1;j<=N;++j)nFloor+=nPerson[j]*(j-i);
if(nFloor<nMinFloor)
        {
            nMinFloor=nFloor;
            nTargetFloor=i;
        }
    }
}

//O(N)，从下到上
void f(int nPerson[],int N,int &nMinFloor,int &nTargetFloor)
{
    nMinFloor=0;
    nTargetFloor=1;
//N1个乘客在第i楼以下，N2个乘客在第i楼，N3个乘客在第i楼以上
int N1=0,N2=nPerson[1],N3=0;
for(int i=2;i<=N;++i)
    {
        nMinFloor+=nPerson[i]*(i-1);
        N3+=nPerson[i];
    }
for(int i=2;i<=N;++i)
    {
if(N1+N2<N3)
        {
            nMinFloor+=N1+N2-N3;
            nTargetFloor=i;
//N1递增
            N1+=N2;            
            N2=nPerson[i];
//N3递减
            N3-=nPerson[i];      
        }
else break;
    }
}

//O(N)，从上到下
void f(int nPerson[],int N,int &nMinFloor,int &nTargetFloor)
{
    nMinFloor=0;
    nTargetFloor=N;
//N1个乘客在第i楼以下，N2个乘客在第i楼，N3个乘客在第i楼以上
int N1=0,N2=nPerson[N],N3=0;
for(int i=N-1;i>=1;--i)
    {
        nMinFloor+=nPerson[i]*(N-i);
        N1+=nPerson[i];
    }
for(int i=N-1;i>=1;--i)
    {
if(N2+N3<N1)
        {
            nMinFloor+=N2+N3-N1;
            nTargetFloor=i;
//N1递减
            N1-=N2;            
            N2=nPerson[i];
//N3递增
            N3+=nPerson[i];      
        }
else break;
    }
}