您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

線性規劃解百度之星電梯問題：從暴力枚舉到數學優化

編輯：關於C

百度之星資格賽題目：大廈有 m 輛電梯，每輛只有上/下兩按鈕（上升 u_i、下降 d_i 層）。從 0 樓乘一輛電梯按 n 次按鈕，不能進入負樓層，求能到達的最低樓層。本文對比暴力枚舉與線性規劃優化。

問題建模

選擇第 i 輛電梯
按 j 次上鍵，n-j 次下鍵
最終樓層：W = j×u_i - (n-j)×d_i = (u_i+d_i)×j - n×d_i
約束：W > 0（不能在第 0 樓或負樓層）
目標：最小化 W

方法一：暴力枚舉（超時）

for (int i = 0; i < m; i++)
    for (long j = 0; j <= n; j++) {
        long W = j * up[i] - (n - j) * down[i];
        if (W > 0) ans = min(ans, W);
    }

時間：O(m × n)
n ≤ 1,000,000 時極慢（秒級）

方法二：線性規劃優化（O(m)）

對固定電梯 i，W = (u_i+d_i)×j - n×d_i 關於 j 單調遞增。

約束 W > 0 ⇒ j > n×d_i / (u_i+d_i)

最小整數 j 為：

j_min = floor(n * d_i / (u_i + d_i)) + 1

代入求 W_min，再取所有電梯的最小值。

優化代碼

long ans = LONG_MAX;
for (int i = 0; i < m; i++) {
    long j = n * down[i] / (up[i] + down[i]) + 1;
    long W = j * up[i] - (n - j) * down[i];
    if (W > 0) ans = min(ans, W);
}
printf("%ld\n", ans);

完整程序（含計時對比）

#include 
#include 
#include 

int main() {
    long n; int m;
    scanf("%ld %d", &n, &m);
    int up[2000], down[2000];
    for (int i = 0; i < m; i++) scanf("%d %d", &up[i], &down[i]);

    // 暴力法計時
    clock_t t1 = clock();
    long ans1 = LONG_MAX;
    for (int i = 0; i < m; i++)
        for (long j = 0; j <= n; j++) {
            long W = j * up[i] - (n - j) * down[i];
            if (W > 0 && W < ans1) ans1 = W;
        }
    clock_t t2 = clock();
    printf("暴力: %ld, 時間: %.2f ms\n", ans1, (double)(t2-t1)*1000/CLOCKS_PER_SEC);

    // 線性規劃法計時
    clock_t t3 = clock();
    long ans2 = LONG_MAX;
    for (int i = 0; i < m; i++) {
        long j = n * down[i] / (up[i] + down[i]) + 1;
        long W = j * up[i] - (n - j) * down[i];
        if (W > 0 && W < ans2) ans2 = W;
    }
    clock_t t4 = clock();
    printf("優化: %ld, 時間: %.2f ms\n", ans2, (double)(t4-t3)*1000/CLOCKS_PER_SEC);

    return 0;
}

樣例驗證

Input:
10 3
15 4
15 12
7 12

Output:
13

電梯 1：j = 10×4/(15+4)+1 = 2, W = 2×15 - 8×4 = 30-32 = -2 (無效)
電梯 2：j = 10×12/27+1 = 5, W = 5×15 - 5×12 = 15
電梯 3：j = 10×12/19+1 = 7, W = 7×7 - 3×12 = 49-36 = 13 ← 最優

複雜度對比

指標	暴力枚舉	線性規劃
時間複雜度	O(m × n)	O(m)
空間複雜度	O(1)	O(1)
n=10⁶ 耗時	~秒級	~微秒級
核心思想	窮舉所有可能	數學單調性 + 邊界推導

進一步優化：內存節省

無需存儲 up[]/down[] 數組，讀入即計算：

long ans = LONG_MAX;
for (int i = 0; i < m; i++) {
    int u, d; scanf("%d %d", &u, &d);
    long j = n * d / (u + d) + 1;
    long W = j * u - (n - j) * d;
    if (W > 0 && W < ans) ans = W;
}