傳送門

拉格朗日乘數法裸題

限制

$$f(\{v\})=\sum _{i=1}^n{k}_i{s}_i(v_i?v_i^{\prime })=E_U$$

求

$$g(\{v\})=\sum _{i=1}^n=\frac{s_i}{v_i}$$

最小值

設

$$\begin{gathered} L(\lambda ,\{v\})=g(\{v\})+\lambda [f(\{v\})?E_U] \\ =\sum _{i=1}^n[\frac{s_i}{v_i}+\lambda k_i{s}_i(v_i?v_i^{\prime }{)}^2]?\lambda E_U \end{gathered}$$

對于$v_i$的偏導數為$0$,跳若干步后

$$k_i(v_i?v_i^{\prime })v_i^2=x$$

二分$x$再二分$v_i$并計算是否為$E_U$即可

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #define MAXN 10005 using namespace std; double s[MAXN],k[MAXN],v[MAXN],v_[MAXN],E; int n; inline double solve(int i,double x) {x/=k[i];double l=0,r=1e5,mid;for (int T=1;T<=100;T++){mid=(l+r)/2;if ((mid-v_[i])*mid*mid<x) l=mid;else r=mid;}return v[i]=l; } inline bool check(double x) {double sum=0;for (int i=1;i<=n;i++){solve(i,x);sum+=k[i]*s[i]*(v[i]-v_[i])*(v[i]-v_[i]);}return sum<E; } int main() {scanf("%d%lf",&n,&E);for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&s[i],&k[i],&v_[i]);double l=0,r=1e5,mid;for (int i=1;i<=100;i++){mid=(l+r)/2;if (check(mid)) l=mid;else r=mid;}double ans=0;for (int i=1;i<=n;i++) ans+=s[i]/solve(i,l);printf("%.8f",ans);return 0; }

總結

以上是生活随笔為你收集整理的【NOI2012】骑行川藏【拉格朗日乘数法】【二分套二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。