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

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

问：电梯停在哪一层楼，能够保证这次乘坐电梯的所有乘客爬楼梯的层数之和最少？

 

解析：

对于一个给定的有序数组 {1,3,5,5,7,9}, 求一个数，使得数组中每个数和这个数的差的绝对值的总和最小。

感觉编程之美的题目都是涉及变量较多，一般类似字符串的DP,要记录的变量也就1个2个,编程之美里的题目都要3个或者3个以上。所以这个题虽然不算难，但实际写出来也是要思考10-20分钟。

对于一个数字n, 假设数组中比n小的有left个，等于n的有mid个，大于n的有right个。用f(n)代表n与数组中每个数差的绝对值之和。有f(n) = m;

当n+1时，设等于n+1的数有midNext个，则此时:
 n+1左边的数有  left+mid个
 n+1右边的数有 right-mid个

相比较f(n)的情况， 位于n+1左边所有数与n+1的差的绝对值，增加了 left+mid
相比较f(n)的情况， 位于n+1左边所有数与n+1的差的绝对值，减少了 right-mid

    f(n+1) = f(n) + left + mid -(right-mid); 
    mid = midNext;

 

/*
 * =====================================================================================
 *
 * Filename: lift.c
 *
 * Description:
 *
 * Version: 1.0
 * Created: 10/25/2012 11:06:16 PM
 * Revision: none
 * Compiler: gcc
 *
 * Author: [e-mail] (),
 * Organization:
 *
 * =====================================================================================
 */
#include <stdlib.h>


#include <stdio.h>
#define MAX 1000
void getFloorNo(int *input, int size){
    int result[MAX] = {0};
    int lcount,mcount,rcount;
    int cur;
    int l,r;
    int i;
    l = r = 0;
    cur = 0;
    lcount = 0;
    rcount = size;
    mcount = 0;
    for(i = 0;i<size;i++){
        r+=input[i];
    }
    result[0] = r;
    for(i=1;i<=input[size-1];i++){
        lcount += mcount;
        rcount -= mcount;
        r -= rcount;
        l += lcount;
        result[i] = l + r;
        printf ( "%d = %d\n",i, result[i] );
        mcount = 0;
        while(input[cur] == i){
            cur++;
            mcount++;
        }
    }
}


/*
 * === FUNCTION ======================================================================
 * Name: main
 * Description:
 * =====================================================================================
 */
    int
main ( int argc, char *argv[] )
{
    int input[] = {1,3,5,5,7,9};
    getFloorNo(input, sizeof(input)/sizeof(int));
    return EXIT_SUCCESS;
} /* ---------- end of function main ---------- */