小飞的电梯调度算法

《编程之美》第1.8节：小飞的电梯调度算法

假设楼层共有N层，电梯停在第x层，要去第i层的乘客数目总数为total[i]，所爬楼梯的总数就是sum{total[i]*|i-x|}，求使得这个和最小的x的值，即电梯停的楼层数。

stop1函数是O(N^2)的算法，就是假设在每层楼停下，计算此时需要爬的楼梯数，如果比最小的少，则赋值。

stop2函数时O(N)时间的算法，这里如果电梯当前层数为i，在i之前的人总的需要爬楼梯数为totalBefore，在i之后需要爬的总楼梯数时totalNum，则在i+1层时，前面需要爬的楼梯数增加了totalBefore+total[i]，后面的人爬楼梯总数减少了totalNum，当然减少之后，totalNum此时应更新为totalNum-=total[i]。这样，当遍历完整个楼层以后就能够得到最优解。

stop3函数比较有意思，也是《编程之美》给出的解法：在第i层停下时，假设有N1个人在第i层以下，有N2个人在第i层，有N3个人在i层以上，假如在第i+1层停，此时增加的向上爬楼梯数为N1+N2，减少的向下爬楼梯数为N3，假如此时N1+N2<N3，那么说明在第i+1层停下，比在第i层停下更能减少大家爬楼梯的总数。

注意stop3中，为什么如果N1+N2<N3的条件不满足就不需要继续执行for循环了：因为N1是线性增加的，N3是线性减少的，如果不满足这个条件，那么接下来随着i增大，也不可能再满足了，因此可以直接跳出循环了，从这个意义上讲，stop3的执行效率还是高于stop2的。

stop4是后面的扩展问题的解，即此时上楼梯需要消耗的能量值为k，下楼梯消耗的能量值为1，求出最佳的停楼梯的地点。如果各层的人数不变，则k越大，求得的电梯停下来的最佳楼层越高，这是显而易见的，假设k为无穷大，则电梯必然是在最高层停下来的。

#include<iostream>
#include<algorithm>
using namespace std;

pair<int,int> stop1(int total[],int N)
{
	int nMinFloor=INT_MAX;
	int targetFloor=0;
	for(int i=0;i<N;i++)//表示在第i层停
	{
		int temp=0;
		for(int j=0;j<N;j++)
		{
			temp+=total[j]*abs(j-i);
		}
		if(temp<nMinFloor)
		{
			targetFloor=i;
			nMinFloor=temp;
		}
	}
	//由于上面的计算是从第0层开始的，因此此处targetFloor要+1
	return pair<int,int>(targetFloor+1,nMinFloor);
}

pair<int,int> stop2(int total[],int N)
{
	int targetFloor=0;
	//N1表示在targetFloor以下的总阶梯数，N2表示在targetFloor层的人数，
	//N3表示在targetFloor以上的总阶梯数
	int N1=0,N2=total[0],N3=0;
	int totalNum=0;
	for(int i=1;i<N;i++)
	{
		N3+=total[i]*i;
		totalNum+=total[i];
	}
	int nMinFloor=N3+N1;
	int totalBefore=N1;
	for(int i=1;i<N;i++)
	{
		totalBefore+=N2;
		N1+=totalBefore;//每上升一个楼层，下面的所有人都增加一层楼梯
		N2=total[i];
		N3-=totalNum;//每上升一个楼层，上面的所有人都减少一层楼梯
		totalNum-=total[i];
		if(nMinFloor>N1+N3)
		{
			nMinFloor=N1+N3;
			targetFloor=i;
		}
	}
	return pair<int,int>(targetFloor+1,nMinFloor);
}

pair<int,int> stop3(int total[],int N)
{
	int N1=0,N2=total[0],N3=0;
	int nMinFloor=0,targetFloor=0;
	for(int i=1;i<N;i++)
	{
		N3+=total[i];
		nMinFloor+=total[i]*i;
	}
	for(int i=1;i<N;i++)
	{
		if(N1+N2<N3)
		{
			targetFloor=i;
			nMinFloor+=N1+N2-N3;
			N1+=N2;
			N2=total[i];
			N3-=N2;
		}
		else
			break;
	}
	return pair<int,int>(targetFloor+1,nMinFloor);
}
//第三个参数k表示上一层楼所花费的能力值，根据实验可以看出，
//k值越大，则合适的楼层数越高。
pair<int,int> stop4(int total[],int N,int k)
{
	int N1=0,N2=total[0],N3=0;
	int nMinFloor=0,targetFloor=0;
	for(int i=1;i<N;i++)
	{
		N3+=total[i];
		nMinFloor+=total[i]*i*k;
	}
	for(int i=1;i<N;i++)
	{
		if(N1+N2<N3*k)
		{
			targetFloor=i;
			nMinFloor+=N1+N2-N3*k;
			N1+=N2;
			N2=total[i];
			N3-=total[i];
		}
		else
			break;
	}
	return pair<int,int>(targetFloor+1,nMinFloor);
}

int hundredRand()
{
	return rand()%100;
}

int main()  
{  
	const int N=56;
	int A[N];
	generate(A,A+N,hundredRand);

	pair<int,int> p=stop1(A,N);
	cout<<p.first<<"	"<<p.second<<endl;
	p=stop2(A,N);
	cout<<p.first<<"	"<<p.second<<endl;
	p=stop3(A,N);
	cout<<p.first<<"	"<<p.second<<endl;
	p=stop4(A,N,2);
	cout<<p.first<<"	"<<p.second<<endl;

    system("pause");  
    return 0;  
}