[NOI 2012] 骑行川藏

目录

题目

传送门

可以发现 \(v>v'\),不然不就骑回去了吗?

解法

首先应该想到的是,\(E\) 与 \(T\) 应该是有函数关系的(注意这里指某一段中)。

可以想到,如果这个函数的 变化率 具有单调性,就可以调整每个函数达到某个最优解(不清楚的话可以康康 这个)。

变化率怎么求?求导!

这里有一个比较简便的方法:将 \(v\) 作为自变量分别计算 \(T,E\) 的导数,然后将其作比。柿子就是:

\[\frac{\Delta T}{\Delta E}=\frac{\Delta T}{\Delta v}\div \frac{\Delta E}{\Delta v} \]

\[=\frac{T'(v)}{E'(v)}=\frac{-s\times v^{-2}}{ks(2v^1-2v'v^0+0)}=\frac{-1}{2kv^2(v-v')} \]

需要注意的是,导数随自变量变化(在这里是 \(E\)),但这里求得的导数随 \(v\) 变化。但由于在本题中这两者单调性相同(有 \(E=ks(v-v')^2\),又因为 \(v>v'\)),故后文可以用 \(v\) 的变化来描述。

由此变化率随 \(E\) 的增大而增大(只不过一直是负的)。这样当最终每一段路的变化率相等时取最优解。

如何证明?假设有两个变化率 \(k_1>k_2\),那么增大 \(E_1\),减小 \(E_2\) 会造成 \(k_1,k_2\) 分别变小/变大直到相等,而增大/减小同样的 \(\Delta E\) 时,由于变化率则有 \(\Delta T_1>\Delta T_2\),我们就可以再减少一点时间。

由上可知变化率更大,\(E\) 更大,所以我们先二分那个变化率。然后由 \(v\) 更大,变化率更大我们可以二分求解每个 \(v\)(当然你也可以用三次方程求根公式)。

代码

#include <cstdio>

#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
    T x=0; int f=1; char s;
    while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
    while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
    return x*f;
}
template <class T> inline void write(const T x) {
    if(x<0) return (void) (putchar('-'),write(-x));
    if(x>9) write(x/10);
    putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}

const int maxn=1e4+5;

int n;
double E,s[maxn],k[maxn],v_[maxn];

double getV(int i,double x) {
	double l=Max(0.0,v_[i]),r=1e5+5,mid;
	for(int times=100;times;--times) {
		mid=(l+r)/2;
		if(-1.0<2*k[i]*mid*mid*(mid-v_[i])*x) l=mid;
		else r=mid;
	}
	return (l+r)/2;
}

double calc(double x) {
	double ret=0;
	rep(i,1,n) {
		double V=getV(i,x);
		ret+=s[i]*k[i]*(V-v_[i])*(V-v_[i]);
	}
	return ret;
}

int main() {
	n=read(9),scanf("%lf",&E);
	rep(i,1,n) scanf("%lf %lf %lf",&s[i],&k[i],&v_[i]);
	double l=-0x3f3f3f3f,r=0,K,ans=0;
	for(int times=150;times;--times)
		if(calc((l+r)/2)<=E) l=(l+r)/2;
		else r=(l+r)/2;
	K=(l+r)/2;
	rep(i,1,n) ans+=s[i]/getV(i,K);
	printf("%.9f\n",ans);
	return 0;
}
上一篇:[[清华集训2012]串珠子]


下一篇:WPS Office 2012兼容全部Office格式,为办公带来了很多便利