NOI2012 骑行川藏解题报告

　　当我还没看别人的解题报告时，我用了三分法做了40%的数据。

　　围观大神的解题报告，要通过100%的数据要用到拉格朗日乘数法求得最值。

　　Wiki上的解释是这样的：Wikipedia

　　Wiki的解释我自己看不太懂，下面这个视频可能让你能对拉格朗日乘数法有更好的认识：麻省理工学院《拉格朗日乘数法》

　　下面介绍一下拉格朗日乘数法是如何工作的：

　　问题：在g(x1, x2, x3, ..., xn) = c的约束条件下，求f(x1, x2, x3, ..., xn)的最值。

　　我们把问题具体化一下：令g(x, y) = xy = 3，f(x, y) = x² + y² ，求f(x, y)的最小值。

　　我们可以猜到，f(x, y)的最小值是6。

　　因为f(x, y)取得最值时受到g(x, y)条件的约束，那么f(x, y)的法向量应当与g(x, y)的法向量相平行。

　　于是我们得到下面的方程组：

　　f_x = λg_x ==> 2x = λy

　　f_y = λg_y ==> 2y = λx

　　g = 3 ==> xy = 3

　　解得λ = ±2 ，代入方程组解得 (x, y) = (3^1/2, 3^1/2) 或 (x, y) = (-3^1/2, -3^1/2)

　　如果你还看得不太明白，那么推荐你看看上面的那段视频。

　　显然到了现在，你就应该明白这道题是怎么回事了。

　　f(v1, v2, v3, ..., vn) = ∑ s_i / v_i

　　g(v1, v2, v3, ..., vn) = ∑ k_is_i(v_i-v_i')²

　　我们有n+1个方程组：

　　-s₁ / v₁² = 2λk₁s₁(v₁-v₁')

　　-s₂ / v₂² = 2λk₂s₂(v₂-v₂')

　　...

　　-s_n / v_n² = 2λk_ns_n(v_n-v_n')

　　g = E

　　下面，我们先二分λ的值，再根据上面n个方程依次二分计算出v1, v2, ..., vn的值，代到g(v1, v2, ..., vn)函数中比较g与E的大小，缩小 λ 的范围。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 #define N 10001
 8 
 9 using namespace std;
10 
11 int n;
12 double E, s[N], k[N], vp[N], v[N], maxv[N], lamada, ans;
13 
14 double getVi(int i, double lam)
15 {
16     double left = vp[i], right = maxv[i], mid;
17     while (right - left >= 1e-13)
18     {
19         mid = (left + right) / (double)2;
20         if (mid == right || mid == left) break;
21         if (mid * mid * 2 * lam * k[i] * (mid - vp[i]) + 1 > 0) left = mid;
22         else right = mid;
23     }
24     return left;
25 }
26 
27 double balance()
28 {
29     double pans = -E;
30     for (int i=1;i<=n;i++)
31         pans += s[i] * k[i] * (v[i] - vp[i]) * (v[i] - vp[i]);
32     return pans;
33 }
34 
35 double getlamada(double left, double right)
36 {
37     double mid;
38     while (right - left >= 1e-13)
39     {
40         mid = (left + right) / (double)2;
41         if (mid == right || mid == left) break;
42         for (int i=1;i<=n;i++) v[i] = getVi(i, mid);
43         double ban = balance();
44         if (ban > 0) right = mid;
45         else left = mid;
46     }
47     return left;
48 }
49 
50 int main()
51 {
52     freopen("bicycling.in","r",stdin);
53     freopen("bicycling.out","w",stdout);
54     scanf("%d%lf",&n,&E);
55     for (int i=1;i<=n;i++)
56     {
57         scanf("%lf%lf%lf",&s[i],&k[i],&vp[i]);
58         maxv[i] = vp[i] + sqrtl(E / s[i] / k[i]);
59     }
60     lamada = getlamada(-1000, -1e-13);
61     ans = 0;
62     for (int i=1;i<=n;i++)
63         ans += s[i] / v[i];
64     printf("%.8lf
", ans);
65     return 0;
66 }

NOI2012 骑行川藏 解题报告

NOI2012 骑行川藏解题报告