「NOI2012」骑行川藏 - 拉格朗日乘数法+二分 | Bill Yang's Blog

「NOI2012」骑行川藏 - 拉格朗日乘数法+二分

题目大意

    在满足约束条件

    时,最小化


题目分析

先做这道题

两个性质:

  • 使用的体力越多越好,故限制条件可改为$\sum_{i=1}^n k_is_i(v_i-t_i)^2=E$。
  • $v_i$一定大于$0$,因为不难证明选择一个非负的$v_i$一定不劣。

然后现在假设你学会拉格朗日乘数法。

根据拉格朗日乘数法,令:

每个维度求偏导:

化简:

因为$k_iv_i^2(v_i-v_i’)>0$,所以此时$\lambda\lt0$。
如果是$v_i’\lt0$,根据前面的性质,$v_i\gt0$,否则可以得到更精确的下界:$v_i\ge v_i’$。

显然$v_i^2(v_i-v_i’)=-\frac{1}{2\lambda k_i}$是单调的,故可以二分$\lambda$,接下来是一个三次函数求根,可以直接代公式$O(1)$算,也可以根据单调性再次二分。

精度开大点,不然样例都过不了。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define double long double
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=10005;
const double eps=1e-12;
int n;
double Eu,v[maxn],v0[maxn],s[maxn],k[maxn];
double Cal(double lambda) {
double sum=0;
for(int i=1; i<=n; i++) {
double Left=fmax(0,v0[i]),Right=INT_MAX;
while(Right-Left>eps) {
double mid=(Left+Right)/2;
if(2*lambda*mid*mid*k[i]*(mid-v0[i])>=-1)Left=mid;
else Right=mid;
}
v[i]=(Left+Right)/2;
sum+=k[i]*(v[i]-v0[i])*(v[i]-v0[i])*s[i];
}
return sum;
}
int main() {
n=Get_Int();
scanf("%Lf",&Eu);
for(int i=1; i<=n; i++)scanf("%Lf%Lf%Lf",&s[i],&k[i],&v0[i]);
double Left=INT_MIN,Right=0;
while(Right-Left>eps) {
double mid=(Left+Right)/2;
if(Cal(mid)<=Eu)Left=mid;
else Right=mid;
}
double mid=(Left+Right)/2;
Cal(mid);
double ans=0;
for(int i=1; i<=n; i++)ans+=s[i]/v[i];
printf("%0.8Lf\n",ans);
return 0;
}
大佬赏瓶冰阔落吧~
0%