【BZOJ2876】【Noi2012】骑行川藏 拉格朗日乘法
题目描述
给你 (n,E,s_i,k_i,v_i')，要求在
[sum_{i=1}^nk_i{(v_i-v_i')}^2s_ileq E
]
的前提下最小化
[sum_{i=1}^nfrac{s_i}{v_i}
]
(nleq 10000,0leq Eleq {10}^8,0<s_ileq {10}^5,0<kleq 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}^nfrac{s_i}{v_i})。
运用拉格朗日乘法，有：
[egin{cases}
sum_{i=1}^nk_i{(v_i-v_i')}^2s_i-E=0\
frac{s_i}{x_i^2}=2lambda k_is_i(x_i-v_i)
end{cases}
]
每个方程左边都是一个在第一象限的双曲线，右边是一条直线。
所以一定有一个交点，且 (lambda>0)。
可以看出，当 (lambda) 增大时，(v_i) 会减小，(G) 也会减小，所以 (G) 随 (lambda) 递减。
所以我们只需要二分 (lambda)，再二分 (v_i)，判断 (G) 的负号即可。
时间复杂度：(的二分次数的二分次数O(n imes lambda ext{的二分次数} imes v_i ext{的二分次数}))
二分上界我也不会算，就随便输了一个({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_JUDGE
char 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;
else
r=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;
else
r=mid;
}
getv(l);
double ans=0;
for(int i=1;i<=n;i++)
ans+=s[i]/v[i];
printf("%.10lf
",ans);
return 0;
}