admin 管理员组

文章数量: 887006

【BZOJ2876】【Noi2012】骑行川藏 拉格朗日乘法

题目描述

　　给你 \(n,E,s_i,k_i,v_i'\)，要求在
\[ \sum_{i=1}^nk_i{(v_i-v_i')}^2s_i\leq E \]
的前提下最小化
\[ \sum_{i=1}^n\frac{s_i}{v_i} \]
　　\(n\leq 10000,0\leq E\leq {10}^8,0<s_i\leq {10}^5,0<k\leq 1,-100<v_i'<100\)

题解

　　显然最优解会把体力浪完，所以约束的不等号可以换成等号。

　　这样就变成了：在 \(G(V)=\sum_{i=1}^nk_i{(v_i-v_i')}^2s_i-E=0\) 的前提下最小化 \(F(V)=\sum_{i=1}^n\frac{s_i}{v_i}\)。

　　运用拉格朗日乘法，有：
\[ \begin{cases} \sum_{i=1}^nk_i{(v_i-v_i')}^2s_i-E=0\\ \frac{s_i}{x_i^2}=2\lambda k_is_i(x_i-v_i) \end{cases} \]
　　每个方程左边都是一个在第一象限的双曲线，右边是一条直线。

　　所以一定有一个交点，且 \(\lambda>0\)。

　　可以看出，当 \(\lambda\) 增大时，\(v_i\) 会减小，\(G\) 也会减小，所以 \(G\) 随 \(\lambda\) 递减。

　　所以我们只需要二分 \(\lambda\)，再二分 \(v_i\)，判断 \(G\) 的负号即可。

　　时间复杂度：\(的二分次数的二分次数O(n\times \lambda\text{的二分次数}\times v_i\text{的二分次数})\)

　　二分上界我也不会算，就随便输了一个\({10}^{10}\)

　　这题精度要求比较高，\(eps\)要设为\({10}^{-14}\)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<cmath>
#include<functional>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
void sort(int &a,int &b)
{if(a>b)swap(a,b);
}
void open(const char *s)
{
#ifndef ONLINE_JUDGEchar str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);
#endif
}
int rd()
{int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;
}
void put(int x)
{if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');
}
int upmin(int &a,int b)
{if(b<a){a=b;return 1;}return 0;
}
int upmax(int &a,int b)
{if(b>a){a=b;return 1;}return 0;
}
const double eps=1e-14;
int n;
double a[10010],k[10010],s[10010],v[10010];
double E;
void getv(double x)
{for(int i=1;i<=n;i++){double l=0,r=1e10;while(r-l>eps){double mid=(l+r)/2;double s1=s[i]/mid/mid;double s2=2*x*k[i]*s[i]*(mid-a[i]);if(s1>s2)l=mid;elser=mid;}v[i]=l;}
}
double calc(double x)
{getv(x);double ans=0;for(int i=1;i<=n;i++)ans+=k[i]*s[i]*(v[i]-a[i])*(v[i]-a[i]);return ans;
}
int main()
{open("bzoj2876");scanf("%d%lf",&n,&E);for(int i=1;i<=n;i++)scanf("%lf%lf%lf",&s[i],&k[i],&a[i]);double l=0,r=1e10;while(r-l>eps){double mid=(l+r)/2;if(calc(mid)>E)l=mid;elser=mid;}getv(l);double ans=0;for(int i=1;i<=n;i++)ans+=s[i]/v[i];printf("%.10lf\n",ans);return 0;
}

转载于:.html

本文标签： BZOJ2876Noi2012骑行川藏 拉格朗日乘法

版权声明：本文标题：【BZOJ2876】【Noi2012】骑行川藏 拉格朗日乘法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361172h1535260.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。