题解洛谷 P2179 【[NOI2012]骑行川藏】

题意为在满足\(\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i\leqslant E_U\)的条件下最小化\(\sum\limits_{i=1}^n\frac{s_i}{v_i}\)

先考虑贪心，因为最小化\(\sum\limits_{i=1}^n\frac{s_i}{v_i}\)，所以\(\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i=E_U\)时为最优情况。

发现是一个有约束的极值问题，考虑用拉格朗日乘数法来解决。

设\(f(v)=\sum\limits_{i=1}^n\frac{s_i}{v_i}\)，\(φ(v)=\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i-E_U\)

设拉格朗日函数为\(L(v,λ)=f(v)+λφ(v)\)

代入得\(L(v,λ)=\sum\limits_{i=1}^n\frac{s_i}{v_i}+λ[\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i-E_U]\)

根据拉格朗日乘数法得，当拉格朗日函数\(L\)梯度为\(0\)时，\(f(v)\)最优

\[\begin{cases}\nabla_{v_1}L(v,λ)=0\\\nabla_{v_2}L(v,λ)=0\\......\\\nabla_{v_n}L(v,λ)=0\\\nabla_λL(v,λ)=0\end{cases}
\]

求偏导后可得（这里将有关\(v\)的写成一个式子了）

\[\begin{cases}\nabla_vL(v,λ)=2λk_i(v_i-v_i^\prime)s_i-\frac{s_i}{v_i^2}=0\\\nabla_λL(v,λ)=\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i-E_U=0\end{cases}
\]

进一步化简后得

\[\begin{cases}2λk_iv_i^2(v_i-v_i^\prime)=1\ (1)\\\sum\limits_{i=1}^nk_i(v_i-v_i^\prime)^2s_i=E_U\ (2)\end{cases}
\]

那么将上面的方程组解出来，即为我们要求的答案。

考虑到在\((1)\)式中\(v_i\)必须大于等于\(v_i^\prime\)，所以为保证式子成立\(λ\)必须大于\(0\)，同时发现\((1)\)式左边关于\(v_i\)单调递增，所以我们二分求出每一个\(v_i\)，再代入\((1)\)式来检验。

但发现\(λ\)的值也不确定，于是要在二分\(v_i\)的外层再套上一层\(λ\)的二分，这里代入\((2)\)式来检验。

实现细节看代码吧。

\(code:\)

#include<bits/stdc++.h>

#define maxn 10010

#define eps 1e-12

using namespace std;

template<typename T> inline void read(T &x)

{

	x=0;char c=getchar();bool flag=false;

	while(!isdigit(c)){if(c=='-')flag=true;c=getchar();}

	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}

	if(flag)x=-x;

}

int n;

double E,ans;

double s[maxn],k[maxn],v[maxn],u[maxn];

double calc(double x)

{

    return x*x;

}

bool judge(double p,double v,double k,double u)

{

    return 2*p*k*calc(v)*(v-u)<=1;

}

bool check(double p)

{

    double e=0;

    for(int i=1;i<=n;++i)

    {

        double l=max(u[i],(double)0),r=1e5,ans;

        while(l+eps<=r)

        {

            double mid=(l+r)/2.0;

            if(judge(p,mid,k[i],u[i])) ans=l=mid;

            else r=mid;

        }

        v[i]=ans;

        e+=k[i]*calc(v[i]-u[i])*s[i];

    }

    return e<=E;

}

int main()

{

	read(n);

    scanf("%lf",&E);

    for(int i=1;i<=n;++i)

        scanf("%lf%lf%lf",&s[i],&k[i],&u[i]);

    double l=0,r=1e5;

    while(l+eps<=r)

    {

        double mid=(l+r)/2.0;

        if(check(mid)) r=mid;

        else l=mid;

    }

    for(int i=1;i<=n;++i) ans+=s[i]/v[i];

    printf("%.8lf",ans);

	return 0;

}

巴特西

题解洛谷 P2179 【[NOI2012]骑行川藏】

最新文章

热门文章

巴特西

题解 洛谷 P2179 【[NOI2012]骑行川藏】

最新文章

热门文章

题解洛谷 P2179 【[NOI2012]骑行川藏】