程式設計之美_006小飛的電梯排程算法

// 電梯停在哪一層樓，能夠保證這次乘坐電梯的所有乘客爬樓梯的層數之和最少？
public class Test_005
{
    // person[i]表示要到第i層的人數,person[0],person[1]預設為空,即沒有人到0,1層
    static int[] person =
    {
            0, 0, 5, 7, 8, 9, 6, 6, 1, 4, 4, 8, 5, 2, 4, 5, 8, 6, 3, 3, 5, 9, 9, 6, 6, 9, 8, 8, 5, 5, 9, 6, 6, 3
    };

    static int stopFloor = 0;// 電梯停的層數
    static int sumFloor = 0;// 乘客爬樓層總和

    static int N = person.length - 1;// 總樓層數

    static int N1 = 0;// 去電梯停留層之下的人數
    static int N2 = 0;// 去電梯停留層的人數
    static int N3 = 0;// 去電梯停留層之上的人數

    /**
     * 計算目标樓層
     * @param person //記錄要到每層的人數
     */
    public static void targetFloor(int[] person)
    {
        // 沒有到1層以上的就不用坐電梯了
        if (null == person || person.length <= 2)
        {
            return;
        }
        // 當電梯停留在第二層的時候
        stopFloor = 2;
        N1 = 0;
        N2 = person[stopFloor];
        for (int i = 3; i <= N; i++)
        {
            N3 += person[i];
            sumFloor += person[i] * (i - stopFloor);
        }
        // 當電梯停留在3層以上的時候
        for (int i = 3; i <= N; i++)
        {
            if (N1 + N2 < N3)
            {
                stopFloor = i;
                N1 = N1 + N2;
                N2 = person[i];
                N3 = N3 - person[i];
                sumFloor += N1 + N2 - N3;
            }
        }
    }

    public static void main(String[] args)
    {
        targetFloor(person);
        System.out.println("停留在:" + stopFloor + " 乘客爬樓層總和:" + sumFloor);
    }
}