BZOJ 2876 NOI2012 騎行川藏：二分答案 + 拉格朗日乘數法

問題大意

n 段路，第 i 段長 s_i，以速度 v_i 行駛消耗體力 k_i(v-v'_i)²s_i。給定體力上限 E，求最大平均速度（即最小總時間）。

數學建模

目標：最小化 Σ s_i / x_i，約束 Σ k_i (x_i - v_i)^2 s_i ≤ E，x_i ≥ v_i。
拉格朗日函數：L = Σ s_i/x_i + λ(Σ k_i (x_i - v_i)^2 s_i - E)。
對 x_i 求導為 0 得：2λ k_i x_i^2 (x_i - v_i) = 1。
對固定 λ，每段最優速度 x_i 由上式唯一決定（函數單調遞增）。

算法流程

1. 外層二分 λ ∈ [0, INF]
2. 內層對每段二分求解 x_i 滿足導數方程
3. 計算總體力消耗，與 E 比較調整 λ
4. 最終用最優 x_i 計算總時間

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10100;
const double INF = 1e9, EPS = 1e-12;
int n; double E, s[MAXN], k[MAXN], v[MAXN], x[MAXN];

double calc(double lambda) {
    double tot = 0;
    for (int i = 1; i <= n; ++i) {
        double l = max(0.0, v[i]), r = INF;
        while (r - l > EPS) {
            double mid = (l + r) / 2;
            if (2 * lambda * k[i] * mid * mid * (mid - v[i]) > 1) r = mid;
            else l = mid;
        }
        x[i] = (l + r) / 2;
        tot += k[i] * (x[i] - v[i]) * (x[i] - v[i]) * s[i];
    }
    return tot;
}

int main() {
    cin >> n >> E;
    for (int i = 1; i <= n; ++i) scanf("%lf%lf%lf", &s[i], &k[i], &v[i]);
    double l = 0, r = INF;
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        if (calc(mid) >= E) l = mid; else r = mid;
    }
    double ans = 0;
    for (int i = 1; i <= n; ++i) ans += s[i] / x[i];
    printf("%.10lf\n", ans);
    return 0;
}

關鍵洞察

• 凸優化問題 → 拉格朗日乘數法轉化為無約束極值
• 導數方程單調 → 內層可二分求解
• 雙層二分：外層找 λ，內層找 x_i
• 精度控制：EPS = 1e-12 足夠滿足輸出 10 位小數

這道題展示了數學建模在算法競賽中的威力：將複雜約束優化轉化為可計算的單調方程組。