BZOJ2876 [NOI2012]骑行川藏

2015.01.04 07:45 Sun| 3 visits oi_2015| 2015_刷题日常| Text

Solution

orz秦岳大神的神奇算法锦囊。。。

据说NOI2012的时候绝大多数人没有做出是因为不会拉格朗日乘数法。拉格朗日乘数法简言之就是当对一个多元函数求极值时可以对其中的每一个变量分别求一阶偏导,得到一组函数。当这些函数的取值均为零时,原函数即可取到极值。若原函数有约束条件,则将其添加参数λ后直接加入原函数,按照上述方法得到一个方程组,再与这一附加条件联立即可解得所有的变量和λ在极值点处的取值。(好像很水的样子?

对于这一道题,易得约束条件:$\sum\limits _{i=1} ^n k_i(V_i-v_i) ^2s_i-E=0$ ,于是得到 $T=\sum\limits _{i=1}^n{s_i\over v_i}+\lambda(\sum\limits _{i=1} ^n k_i(V_i-v_i) ^2s_i-E))$ 。运用拉格朗日乘数法得到一组方程后二分λ的取值,再通过解出每一个 $V_i$ 的取值(可二分求解)简单判定即可。

另外题目里面明明说 $s_i>0$ 可是为什么选取上下界的时候不特判会TLE……

Code

#include <bits/stdc++.h>
using namespace std;
#define N 10005
#define eps 1e-12
#define sqr(x) ((x)*(x))

int n;
double e, ans, s[N], k[N], v[N];

int main()
{
    cin >> n >> e;
    for(int i=1; i<=n; i++)
        cin >> s[i] >> k[i] >> v[i];
    double l=0, r=1000;
    while(r-l > eps)
    {
        double mid = (l+r)/2, sum = 0; ans = 0;
        for(int i=1; i<=n; i++)
        {
            double lv = v[i], rv = s[i] ? sqrt(e/k[i]/s[i])+v[i] : 0;
            double t = 2*mid*k[i];
            while(rv-lv > eps)
            {
                double midv = (lv+rv)/2;
                if((midv-v[i])*sqr(midv)*t > 1.0)
                    rv = midv;
                else lv = midv;
            }
            sum += sqr(lv-v[i])*s[i]*k[i];
            ans += s[i]/lv;
        }
        if(sum > e) l=mid;
        else r=mid;
    }
    cout << fixed << setprecision(10) << ans <<endl;
}