P2179 [NOI] 骑行川藏 题解

0x01 分析题目

做题首先要排除文中的冗余信息，用最短的语言描述一道题。

对于这道题，我们可以在阅读后得到这样的三条信息：

E i = k i ( v i − v i ′ ) 2 s i E_i = k_i(v_i-v_i^{'})^2s_i Ei​=ki​(vi​−vi′​)2si​

∑ i = 1 n E i ≤ E \sum_{i=1}^{n}E_i \leq E ∑i=1n​Ei​≤E

要求 t t t 尽可能小。

0x02 做法的推导

初步分析完后，我们就要着手从初始条件开始推答案。

在两条初始信息中，信息 3 是和答案有关的,信息 1、2 是约束条件，所以我们的思路自然转移到如何将约束条件与答案关联到一起。

使用脑子思考可以得到一个结论：

每段路上消耗的能量（做的功） E i E_i Ei​ 越大，消耗的时间 t i t_i ti​ 越小。

上面这句话换种方式表达，就有了：

我们可以在某段路上增加能量以缩短时间。（推论 1）

有了推论 1，我们就将约束条件与答案关联到一起了。

但又由推论 1 引出了一个新的问题：在哪条路上增加能量呢？

由于增加某条路的能量不会干扰到另一条路，所以我们可以贪心的想：

把能量加到价值（或说性价比）最高的路上去。

那对于一条路来说，此刻增加能量的价值又如何体现呢？

显然是增加的时间。

于是我们很容易想到：若时间是关于能量的函数，那么函数在 E i E_i Ei​ 处的切线的斜率，也就是导数，就是在此条路增加能量的价值（性价比）。

推论 1 告诉我们： t t t 随 E E E 的增大而减小。

由此可以知道：价值（或性价比）只会越来越小。

我们总会将能量加到性价比大的路段上去，不断如此操作，我们可以想象最后所有路的价值（或性价比）会是一个相同值！

于是我们可以开始推式子了！

d t d E = x \frac{dt}{dE} = x dEdt​=x

x x x 为最后的公共导数。

因为 E i = k i ( v i − v i ′ ) 2 s i E_i = k_i(v_i-v_i^{'})^2s_i Ei​=ki​(vi​−vi′​)2si​，且 t t t 也可以表达为关于 v v v 的函数 t = s v t=\frac{s}{v} t=vs​。

所以：

d t d E = d t d v d v d E = d t d v / d E d v = x \frac{dt}{dE} = \frac{dt}{dv}\frac{dv}{dE} = \frac{dt}{dv} / \frac{dE}{dv} = x dEdt​=dvdt​dEdv​=dvdt​/dvdE​=x

d t d v = − s v 2 , d E d v = 2 k s ( v − v ′ ) \frac{dt}{dv} = -\frac{s}{v^2} , \frac{dE}{dv} = 2ks(v-v^{'}) dvdt​=−v2s​,dvdE​=2ks(v−v′)

所以：

− s 2 k s v 2 ( v − v ′ ) = x -\frac{s}{2ksv^2(v-v^{'})} = x −2ksv2(v−v′)s​=x

如果我们知道了公共导数 x x x，就可以解出每段路的 v v v 值（懒得解方程？直接二分 v v v 不就行了）。

知道了每段的 v v v 值，就可以检验当前的 x x x 是否可行。

于是， x x x 也可以二分了。

最后看看代码，就很容易明白了。

代码：

#include<bits/stdc++.h>#define int long longusing namespace std;int n;double s[10005], k[10005], u[10005];double e;double solve(double x, int i) {//公共导数x与当前路段idouble l = 0, r = 100005, v;//题目保证v<=100005int batch = 60;//浮点数二分的批次while(batch--) {v = (l + r) / 2;if(2 * k[i] * s[i] * x * v * v * (v - u[i]) > -s[i]) l = v;//刚推导出来的式子稍加变形else r = v;}v = (l + r) / 2;//最后得到结果return v;}double work(double x) {//二分出的公共导数得到的能量总值double sum = 0;for(int i = 1; i <= n; i++) {double v = solve(x, i);sum += k[i] * s[i] * (v - u[i]) * (v - u[i]);}return sum;}signed main() {cin>>n>>e;for(int i = 1; i <= n; i++) {cin>>s[i]>>k[i]>>u[i];}double l = -0x3f3f3f, r = 0, dc;//注意：函数t呈下降趋势，导数显然为负int batch = 100;while(batch--) {dc = (l + r) / 2;if(work(dc) <= e) l = dc;else r = dc;}dc = (l + r) / 2;double ans = 0;for(int i = 1; i <= n; i++)ans += s[i] / solve(dc, i);printf("%.12lf\n", ans);return 0;}

如果觉得《P2179 [NOI] 骑行川藏 题解》对你有帮助，请点赞、收藏，并留下你的观点哦！