百度之星資格賽真題：電梯按鈕優化問題的線性規劃數學建模與 O(m) 解法

題目大意

百度新大廈有 m 部電梯，第 i 部電梯只有兩個按鈕：上行 u_i 層、下行 d_i 層。大廈無上限 (無頂層)，有下限 (0 層地面，不可進入負樓層)。
你在 0 居選擇一部電梯，連續按鈕 n 次 (每次二選一)。求可能到達的最低樓層數 (嚴格 > 0)。

約束：1 ≤ n ≤ 1,000,000, 1 ≤ m ≤ 2,000, 1 ≤ u_i, d_i ≤ 1000。

朴素暴力解法 (超時)

枚舉每部電梯，枚舉上行次數 j = 0..n，下行 n-j 次，計算樓層 floor = j*u - (n-j)*d，取滿足 floor > 0 的最小值。
複雜度 O(m × n)，n=1e6, m=2000 時達 2×10⁹ 次循環，不可行。

數學建模：線性規劃視角

固定某部電梯 (u, d)。設上行 x 次，下行 y 次。
約束：

• x + y = n (總按鈕次數)
• x, y ≥ 0 且為整數
• floor = u*x - d*y > 0 (最終樓層為正)

目標：最小化 floor。

代數求解

代入 y = n - x：

floor = u*x - d*(n - x) = (u + d)*x - d*n

要求 floor > 0：

(u + d)*x - d*n > 0
=> x > d*n / (u + d)

由於 x 為整數，滿足條件的最小 x 為：

x_min = floor(d*n / (u + d)) + 1

注意：若 d*n % (u+d) == 0，即除盡，x = d*n/(u+d) 時 floor = 0 (恰好回到 0 層)，題目要求 > 0，故仍需 +1。公式統一適用。

對應最小樓層：

floor_min = (u + d)*x_min - d*n

O(m) 最優算法

對每部電梯獨立計算 x_min 和 floor_min，取全局最小。
複雜度 O(m)，m=2000 瞬間完成。

完整 AC 代碼 (C/C++)

#include 
#include 

int main()
{
    long long n;  // n up to 1e6, 但乘積 d*n 可達 1e9, 用 64位
    int m;
    while (scanf("%lld%d", &n, &m) == 2) {
        long long best = LLONG_MAX;
        for (int i = 0; i < m; i++) {
            long long u, d;
            scanf("%lld%lld", &u, &d);
            // 計算最小上行次數 x
            long long x_min = (d * n) / (u + d) + 1;
            // 計算對應樓層
            long long floor = (u + d) * x_min - d * n;
            if (floor > 0 && floor < best)
                best = floor;
        }
        printf("%lld\n", best);
    }
    return 0;
}

關鍵細節

1. 64 位整數：d*n 最大 1000×1,000,000 = 10⁹，(u+d)*x_min 同量級，32 位 int (2.1×10⁹) 勉強夠但臨界，務必用 long long。
2. 整除向下取整：C/C++ 整數除法自動向零截斷，對正數即向下取整，符合 floor 語義。
3. +1 的必要性：嚴格大於 0。若 d*n % (u+d) == 0，不加 1 會得到 floor=0 (非法)。
4. 獨立電梯：題目規定「選擇一部電梯」，不可中途換乘，故各電梯獨立計算取最優。
5. 無解情況：理論上 x_min ≤ n 總能滿足 (取 x=n 時 floor = u*n > 0)，故必有解。

測試用例驗證

輸入:
10 3
15 4
15 12
7 12

計算:
電梯1: u=15,d=4, n=10
  x_min = (4*10)/(19) + 1 = 40/19 + 1 = 2 + 1 = 3
  floor = 19*3 - 40 = 57 - 40 = 17
電梯2: u=15,d=12
  x_min = (12*10)/27 + 1 = 120/27 + 1 = 4 + 1 = 5
  floor = 27*5 - 120 = 135 - 120 = 15
電梯3: u=7,d=12
  x_min = (12*10)/19 + 1 = 120/19 + 1 = 6 + 1 = 7
  floor = 19*7 - 120 = 133 - 120 = 13  ← 最小

輸出: 13  ✅ (與樣例一致)

進階思考：若允許中途換電梯？

若可在任意時刻切換電梯，問題變為：在 n 步中，每步從 {+u_i, -d_i} 中選一個動作，使最終位置 > 0 且最小。這是有向圖最短路 / DP 問題，狀態 dp[step][floor]，複雜度高得多。但本題明確限定「選一部電梯」，線性規劃完美適用。

總結

這道題是「算法競賽中數學建模威力」的經典教案：

1. 識別決策變量：上行次數 x (下行由總步數決定)。
2. 建立線性目標函數與約束：floor = (u+d)x - dn, x > dn/(u+d)。
3. 解析求解：直接公式 x_min = floor(dn/(u+d)) + 1，消除循環。
4. 複雜度從 O(mn) 降至 O(m)，輕鬆應對大數據範圍。

面對大規模枚舉問題，先嘗試代數化簡、凸優化、貪心證明，往往能發現 O(1) 或 O(log n) 的數學解法，避開暴力計算陷阱。