admin 管理员组文章数量: 887017
【BZOJ2876】【NOI2012】骑行川藏（数学，二分答案）
题面
BZOJ
题解
我们有一个很有趣的思路。
首先我们给每条边随意的赋一个初值。
当然了，这个初值不会比这条边的风速小。
那么，我们可以先计算一下当前所需要的总能量。
剩下的能量我们分成若干等份。
每次从所有的边中，选择一个加了这一份能量后，时间减少最多的那条边，让他提速。
直到我们所有的能量都分配完，此时答案一定最优。
所以，可以简化一下题意。
在 ∑ks(v′−v)2=EU ∑ k s ( v ′ − v ) 2 = E U 的情况下，最小化 ∑sv ∑ s v
然后剩下的部分我就去看看学长写的吧（因为我也不懂）
MashiroSky’s Blog
主要是不知道为什么梯度向量就平行了
补充一下自己的几点理解：
首先能量和等于 EU E U 是一个函数，我们可以把它先在空间中表示出来。
然后最小化的值我们也可以看成一个函数，那么我们类似于地理中的等高线，
把所有等值的点的位置一圈一圈的全部向外拓展，当它第一次与能量构成的函数相交时，
并且这个交点一定是切点，此时取到的就是最小值了。
梯度向量由偏向量构成，其中偏向量的每一维分别对应这这个函数在每一维上的导数。
也就是把每一维分别看做主元，其他的都看作常量后求导。
也许梯度向量相等可以看做为在切点处，任何一维的增长量都相等？
假设我们默认梯度向量平行
那么，就有 (v1,v2,v3....,vn)=λ(v′1,v′2,...,v′n) ( v 1 , v 2 , v 3 . . . . , v n ) = λ ( v 1 ′ , v 2 ′ , . . . , v n ′ )
我们可以二分这个 λ λ ，然后求解出所有的速度。
求解速度的时候等价于解方程 2λKv2(v−v′)=−1 2 λ K v 2 ( v − v ′ ) = − 1
所有已知量都挪到右边，假设算完后的结果是 c c
那么就是
我们找左边的零点，发现显然只有两个零点 v′ v ′ 和 0 0
并且我们最终的速度一定不会小于
解的下界是 max(0,v′) m a x ( 0 , v ′ )
差不多就这些了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAX 11111
#define eps 1e-13
int n;
double Eu,S[MAX],K[MAX],V[MAX],v[MAX],ans;
bool check(double lam)
{double ret=0;for(int i=1;i<=n;++i){double l=max(0.0,V[i]),r=1e9,c=-1/(2*lam*K[i]);v[i]=l;while(l+eps<=r){double mid=(l+r)/2;if(mid*mid*(mid-V[i])<c)l=mid;else r=mid;}v[i]=l;ret+=K[i]*S[i]*(V[i]-v[i])*(V[i]-v[i]);}return ret<=Eu;
}
int main()
{scanf("%d%lf",&n,&Eu);for(int i=1;i<=n;++i)scanf("%lf%lf%lf",&S[i],&K[i],&V[i]);double l=-1e9,r=0,ret;while(l+eps<=r){double mid=(l+r)/2;if(check(mid))l=mid,ret=mid;else r=mid;}check(ret);for(int i=1;i<=n;++i)ans+=S[i]/v[i];printf("%.10lf\n",ans);return 0;
}
本文标签： BZOJ2876NOI2012骑行川藏（数学，二分答案）
版权声明：本文标题：【BZOJ2876】【NOI2012】骑行川藏（数学，二分答案） 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732361594h1535371.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论