原帖地址：http://blog.csdn.net/li4951/article/details/7486092
亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：
由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。
问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？
解法一：暴力枚举法。从第1层枚举到第N层，求出电梯在x层停的话，所有乘客需要怕多少层楼。求出最少的那层即可。代码略。
解法二：动态规划。假设电梯停在第x层，已知目的楼层在x层的有N2人，在x层以下的有N1人，在x层以上的有N3人。此时总花费为sum。则往上走一层的话，总花费变为sum + N2 + N1 - N3。那么初始状态电梯停在第一层，向上进行状态的变迁，开始时N2 + N1 - N3 < 0。sum越来越小，直到某一层N2 + N1 >= N3，就没有必要在往上走了。这时已求出最合适的楼层了。
解法三：我的方法。哈哈。其实没有那么复杂。假设只有两个人，一个去9层，一个去2层，那么不管电梯停在2至9层中间的任何楼层，两个人的总花费都是7.就比如在数轴上点2和点9中间的任何点距离2和9的距离之后都是7。那么停在哪都无所谓了。接着我们扩展开来，假设有N个人，他们的目标楼层分别是2,3,3,4,5,5,5,7,7,8,9。按我们的想法，对于两端的（2,9）电梯只要停在他们之间都一样。同理对于（3,8）电梯只要停在他们中间都一样……。最终电梯只要停在中间那个数即可。也就是中位数。原来弄半天只需求出中位数即可啊。如果N是偶数个的话，停在中间那两个数任何一个都可以的。欢迎大家对我的解法拍砖。代码就不用了吧。
扩展问题的解法：
如果往上爬楼梯比较累，往下走较容易，假设往上走一层耗费k单位的能量，往下走一层只耗费1单位的能量。此时就不适合用我的解法三了，解法二更加适合。代码如下：
- int controlElevator(int nPerson[], int nfloor, int upWeight){
- int targetFloor = 1;
- int minFloor = 0;
- int N1 = 0;
- int N2 = nPerson[1];
- int N3 = 0;
- int i = 0;
- for(i = 2; i <= nfloor; i++){ //i表示大众意义上的第i层
- N3 += nPerson[i];
- minFloor += (nPerson[i] * (i - 1) * upWeight);
- }
- for(i = 2; i <= nfloor; i++){
- if(N1 + N2 < N3 * upWeight){
- minFloor += (N1 + N2 - N3 * upWeight);
- N3 -= nPerson[i];
- N1 += N2;
- N2 = nPerson[i];
- targetFloor = i;
- }
- else
- break;
- }
- return minFloor;
- // return targetFloor;
- }
原贴地址：http://blog.csdn.net/lonelycatcher/article/details/7910877
亚洲微软研究院所在的希格玛大厦一共有6部电梯。在高峰时间，每层都有人上下，电梯每层都停。实习生小飞常常会被每层都停的电梯弄的很不耐烦，于是他提出了这样一个办法：
由于楼层并不算太高，那么在繁忙的上下班时间，每次电梯从一层往上走时，我们只允许电梯停在其中的某一层。所有乘客从一楼上电梯，到达某层后，电梯停下来，所有乘客再从这里爬楼梯到自己的目的层。在一楼的时候，每个乘客选择自己的目的层，电梯则计算出应停的楼层。
问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？
方法一：暴力枚举，时间复杂度O(N^2)
- /*
- * O(N^2)
- */
- int N;
- int nPerson[N+1];
- int target_floor;
- int min_floors = INT_MAX;
- for(i = 1;i<=N;i++)
- {
- int sum_floors = 0;
- for(j = 1;j<=N;j++)
- {
- sum_floors += nPerson[j] * abs(j - i);
- }
- if(sum_floors < min_floors)
- {
- min_floors = sum_floors;
- target_floor = i;
- }
- return (target_floor);
- }
方法二：书上提供的O(N)的动态规划的算法。
假设电梯停在i层楼，可以计算出所有乘客要爬楼层的层数为Y,假设此时有N1个乘客在i层楼以下，N2个乘客在I层楼，N3个乘客在I层楼以上，则当电梯停在i+1层的时候，N1+N2个乘客要多下一层楼，共多下N1+N2层，N3个乘客要少往上面爬一层楼，少上N3层楼，此时Y(i+1) = Y(i) + N1+N2-N3，很显然，当N1+N2<N3的时候，Y不断减小。Y1很容易算出来，另外我们还可以看出，N1+N2是递增的，N3是递减的，所以N1+N2一旦大于N3的时候，我们直接退出循环即可，没有必要再计算下去了。
- /*
- O(N) dp
- */
- int N;
- int nPerson(N+1);
- int target_floor = 1;
- int min_floors = 0;
- int N1 = 0,N2 = nPerson[1],N3 = 0;
- for(i = 2;i<=N;i++)
- {
- min_floors += nPerson[i] * (i-1);
- N3 +=nPerson[i];
- }
- for(i = 2;i<=N;i++)
- {
- if(N1+N2 < N3)
- {
- target_floor = i;
- min_floors +=(N1+N2-N3);
- N1 +=N2;
- N2 = nPerson[i];
- N3 -=nPerson[i];
- }
- else
- break;
- }
- return target_floor;
其实这道题目仔细分析起来就是求一组数据的中位数而已。假设两人，分别到3层楼和8层楼下，在3和8之间取一点，使得到两个点距离最小，很显然，在3和8中的每一点到3和8的距离之和都是相等的。推广到2 3 5 5 6 7 8 8 9这样一组数据，target_floor为中位数。
- /*
- * mid_value
- *
- */
- int nPerson[N+1];
- int target_floor;
- int left = 1,right = N;
- while(right-left > 1)
- {
- while(nPerson[left] == 0)left++;
- nPerson[left] --;
- while(nPerson[right--] == 0)right--;
- nPerson[right] --;
- }
- return left;
扩展问题，往上爬一层要耗费K个单位的能量，往下走耗费1个单位的能亮，只需要计算N1+N2-N3变成N1+N2-N3*K即可。其余的都是一样的。
---------------------------------------------------------------------------------------------------------------------------------------------------------------
原帖地址：http://blog.csdn.net/zhanglei0107/article/details/8150437
设有N2个乘客在第i层下，N1个乘客的目的地楼层在第i层以下，N3个乘客的楼层在第i层以上
假设电梯从停在i层改停在为i+1层，停在第i层时消耗的总能量为E
则改为i+1层停之后原先i层以上的乘客即N3个乘客少往上爬一层，原先第i层的N2个乘客需多往下爬一层，原先第i层以下的N1个乘客需多往下爬一层。
所需总能量变为E-N3*K+N1+N2
若N3*K>(N1+N2)，则停在i+1层好
若停第i层比停i+1层能量消耗低，会出现停第i层比停第i+2层能量消耗多的情况么
已知 N3*K<(N1+N2)
从i层到i+2层
消耗的能量变为E+2(N1+N2)+nPersons[i+1]-k(N3-nPersons[i+1])>E
因此循环只要有一次停第i层比停i+1层能量消耗低，后面变无需再比较
- //nPerson[i]表示到第i层的乘客数目
- //N1代表目标楼层在第i层以下的乘客数
- //N2代表目标楼层第i层的乘客数
- //N3代表目标楼层在第i层以上的乘客数
- void (int *nPerson,int k){
- int nMinEnergy=0;
- int nTargetFloor=1;
- int N1,N2,N3;
- int i;
- for(N1=0,N2=nPerson[1],N3=0,i=2;i<N;i++)
- {
- N3+=nPerson[i];
- nMinEnergy+=nPerson[i]*(i-1)*k;
- }
- for(i=2;i<N;i++)
- {
- if(N3*k>(N1+N2)){
- nTargetFloor=i;
- nMinEnergy=nMinEnergy-N3*K+N1+N2;
- N1=N1+nPerson[i-1];
- N3-=nPerson[i];
- N2=nPerson[i];
- }
- else
- break;
- }
- }
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
【原创】编程之美---小飞的电梯调度问题 （停k层的解法）
问题.有一栋楼，一共有N层，要去每一层的人分别是A[1],A[2]....A[N]，如果电梯可以停K次，问停在哪K层让所有人走的矩离最短？[备注：这只是我的个人解法，欢迎和我讨论]
解法：
用一个数组opt[i][j]记录电梯前i次停在1到j层之间，所有人走的路的最短矩离。用cost[i][j]记录如果电梯从第i层到第j层只能停一次，电梯停在最佳位置让所有人走的矩离最短的最优解。那么cost[i][j]怎么求呢？（这里把这个解法省略，具体可参见编程之美“小飞的电梯调度”）。如果前i次停留在前j层，那么第i+1次停留在第j+1至j+k层(j+k<=n)，则状态转移方程为
opt[i+1][j+k]=min{opt[i][j]+cost[j+1][j+k];} (k+j<=n)
Cost数组存放电梯从第i层到j层停一次的最小走动矩离，构造cost的代码如下：
for(i=1;i<=m;i++)
for(j=i;j<=m;j++)
{
cost[i][j] = 0;
mid = 求得电梯在i到j层的最佳停留位置;
for(k=i;k<=j;k++)
cost[i][j]+=(distance[mid]-distance[k])>=0 ?
distance[mid]-distance[k]:distance[k]-distance[mid];
}Opt[i][j] 表示从电梯在第1层到第j层停i次所有人的最小走动矩离，对于i=1（即电梯只停一次的情况）来说，opt[i][j] = cost[i][j],如果让电梯在1 至 j层停两次，也就是i=2的情况，可能是下面一种情况的最优解：
第一次停在第一层，第二次停在2至j层；
第一次停在1至2层，第二次停在3至j层；
第一次停在1至3层，第二次停在4至j层；
等等。。。。。
该部分的代码如下：
for(i=0;i<=n;i++)
for(j=0;j<=m;j++)
if(opt[i][j]<Integer.max)
{
for(k=1;j+k<=m;k++)
{
if(opt[i+1][j+k]>opt[i][j]+cost[j+1][j+k])
{
opt[i+1][j+k] = opt[i][j]+cost[j+1][j+k];
}
}
}