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

题目大意

    在满足约束条件

$$\sum_{i=1}^n k_is_i(v_i-v_i')^2\leq E$$

    时，最小化

$$\sum_{i=1}^n s_i/v_i$$

---

题目分析

先做这道题

两个性质：

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

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

$$f(v_1,v_2,\ldots,v_n)=\sum_{i=1}^n s_i/v_i$$ $$g(v_1,v_2,\ldots,v_n)=\sum_{i=1}^n k_is_i(v_i-v_i')^2=E$$

根据拉格朗日乘数法，令：

$$L(v_1,v_2,\ldots,v_n,\lambda)=f(v_1,v_2,\ldots,v_n)+\lambda(g(v_1,v_2,\ldots,v_n)-E)$$

每个维度求偏导：

$$-\frac{s_i}{v_i^2}=2\lambda k_is_i(v_i-v_i')$$ $$\sum_{i=1}^nk_i(v_i-v_i')^2s_i=E$$

化简：

$$2\lambda k_iv_i^2(v_i-v_i')=-1$$

因为$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)$算，也可以根据单调性再次二分。

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

---

代码

#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;
}