开车旅行
前情提要
如果您觉得这篇题解有用,希望可以点一个赞。
如果你同时也认可 Aigrl 的其他分享的话,希望也可以点一个关注!
第一步 分析题目
题面 :
小 $A$ 和小 $B$ 决定利用假期外出旅行,他们将想去的城市从 $1$ 到 $N$ 编号,且 编号较小的城市在编号较大的城市的西边,已知各个城市的海拔高度互不相同,记城市 $i$ 的海拔高度为 $H_i$。
城市 $i$ 和城市 $j$ 之间的距离 $d[i,j]$ 恰好是这两个城市海拔高度之差的绝对值,即 $d[i,j]=|Hi−Hj|$。
旅行过程中,小 $A$ 和小 $B$ 轮流开车,第一天小 $A$ 开车,之后每天轮换一次。
每个人每天均会从一个城市出发走到另一个城市。
他们计划选择一个城市 $S$ 作为起点,一直向东行驶,并且最多行驶 $X$ 公里就结束旅行。
小 $A$ 和小 $B$ 的驾驶风格不同,小 $B$ 总是沿着前进方向选择一个最近的城市作为目的地,而小 $A$ 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。
如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 $X$ 公里,他们就会结束旅行。
分析:
首先,我们可以发现对于小 $A$ 和 小 $B$而言,其中任何一个城市都只能到达 离此城市最近的两个城市。
也就是说,虽然从任何一个城市出发都可以走到每个城市,但只有到最近两个城市的路是有效的。
同时,因为 城市 $i$ 和城市 $j$ 之间的距离 $d[i,j]$ 是这两个城市海拔高度之差的绝对值。
所以,可以等价于 邻值查找 一题。
即在一有序序列中,找到最接近这个点的值和第二接近这个点的值。
这个问题有多个解决方法,在这里作者是用二叉查找树 $set$ 实现的。
如果你不清楚 $set$ 和其基本操作的话,可以去搜一下。
set<City>::iterator q = Q.lower_bound(now); // 返回的是地址,设为基准 0
q --; // -1
int Li = (*q).id, Lw = (*q).w;
q ++, q ++; // 1
int Ri = (*q).id, Rw = (*q).w;
q --; // 0
结合代码,我们可以得出,q 是 指针, 所以需要解除引用,而 q - -, q ++, 就是搜其前一个数和后一个数
而小 $B$ 要走的就是 $min(L_i, R_i)$,
if (abs(Rw - h[i]) >= abs(h[i] - Lw))
{
Cb = Li;
q --, q --;
if (abs(Rw - h[i]) >= abs(Rw - (*q).w))
Ca = (*q).id;
else
Ca = Ri;
}
else
{
Cb = Ri;
q ++, q ++;
if (abs((*q).w - h[i]) >= abs(h[i] - Lw))
Ca = Li;
else
Ca = (*q).id;
}
小 $A$ 要走的就复杂了些许,即在 $min([q-2], [q-1], [q+1], [q+2])$ 中。
以上就是预处理的内容了。
接下来的部分,需要一定的基础,如果您自认不足的话,可以关注一下我的其它内容(求关注)。
题面 :
每个人每天均会从一个城市出发走到另一个城市。
他们计划选择一个城市 $S$ 作为起点,一直向东行驶,并且最多行驶 $X$ 公里就结束旅行。
小 $A$ 和小 $B$ 的驾驶风格不同,小 $B$ 总是沿着前进方向选择一个最近的城市作为目的地,而小 $A$ 总是沿着前进方向选择第二近的城市作为目的地(注意:本题中如果当前城市到两个城市的距离相同,则认为离海拔低的那个城市更近)。
如果其中任何一人无法按照自己的原则选择目的城市,或者到达目的地会使行驶的总距离超出 $X$ 公里,他们就会结束旅行。
分析 :
我们可以看到题面要求 总距离不能超过 $x$, 从而联想到 二分 和 二进制拆分(倍增)
题面
在启程之前,小 $A$ 想知道两个问题:
-
对于一个给定的 $X=X_0$,从哪一个城市出发,小 $A$ 开车行驶的路程总数与小 $B$ 行驶的路程总数的比值最小(如果小 $B$ 的行驶路程为 $0$,此时的比值可视为无穷大,且两个无穷大视为相等)。如果从多个城市出发,小 $A$ 开车行驶的路程总数与小 $B$ 行驶的路程总数的比值都最小,则输出海拔最高的那个城市。
-
对任意给定的 $X=X_i$ 和出发城市 $S_i$,求出小 $A$ 开车行驶的路程总数以及小 $B$ 行驶的路程总数。
分析 :
我们需要先明确我们要计算哪些信息,显然是小 $A$ 开车行驶的路程总数与小 $B$ 开车行驶的路程总数。
问题 $1$, 只需要在枚举的起点都计算一遍最小比值就可以了。
第二步 思路综合与优化
首先,我们可以发现从任意一个点出发,其最小点和次小点是固定的。
所以可以通过 $log$ 级算法快速求解,由于二分不好判定,于是我们改用倍增来计算。
因为二进制拆分思想可以让我们只需要预处理 $2$ 的次方就可以最后组合。
那么,我们需要先知道哪些信息才能倍增呢?
$f[i][j][k]$ 从城市 $j$ 出发,行驶 $2^i$ 天, $k$ 先开车,最终会到达的城市
$Da[i][j][k]$ 从城市 $j$ 出发,行驶 $2^i$ 天, $k$ 先开车,小 $A$行驶的路程长度
$Db[i][j][k]$ 从城市 $j$ 出发,行驶 $2^i$ 天, $k$ 先开车,小 $B$行驶的路程长度
其中 $k=0$ 表示小 $A$ 先开车,$k=1$ 表示小 $B$ 先开车
显然我们可以倍增天数来计算这个最值问题,且复杂度在 $log$ 级别。
问题解决(状态转移方程)
现在最大的一个难题就是如何预处理这三个数组。
因为我们已经知道小 $A$、小 $B$ 从 任意城市 出发会走到的城市是什么。
所以可得 :
f[0][j][0] = Ca, f[0][j][0] = Cb;
// 小 A, 小 B 从城市 j 出发会走到的城市
Da[0][j][0] = abs(h[j] - h[Ca]); // 小 A 走过的总距离
Db[0][j][1] = abs(h[j] - h[Cb]); // 小 B 走过的总距离
然后就要推一下状态转移公式是什么了,
当 $i = 1$ 时, 我们可得方程
f[1, j, k] = f[0, f[0, j, k], k ^ 1];
其中 $f[0][j][k]$ 为第 $j$ 个城市的下一个城市,$k$ ^ $1$ 是因为走过的天数不为奇数时驾驶员会换人。
Da[1, j, k] = Da[0, j, k] + Da[0, f[0, j, k], k ^ 1];
Db[1, j, k] = Db[0, j, k] + Db[0, f[0, j, k], k ^ 1];
意思是先从 $j$ 往后走一步的位置变了一个驾驶员再走一步
其中 $f[0][j][k]$ 是位置的变化
当 $i > 1$ 时, 我们可得方程
f[i, j, k] = f[i - 1, f[i - 1, j, k], k];
从 $j$ 往后走 $2 ^ {i - 1}$ 到的城市,再往后走 $2 ^ {i - 1}$ 步,
因为 $i = 1$ 时已经变过驾驶员,所以天数为偶数时不用再变了
Da[i, j, k] = Da[i - 1, j, k] + Da[i - 1, f[i - 1, j, k], k];
Db[i, j, k] = Db[i - 1, j, k] + Db[i - 1, f[i - 1, j, k], k];
与上面同理。
问题解决(倍增)
我们需要求出从 S 点出发,距离不超过 X 的情况下小 $A$ 开车行驶的路程总数与小 $B$ 开车行驶的路程总数。
void calc(int S, int X)
{
int p = S;
Ao = Bo = 0;
for (int i = 18; i >= 0; i -- )
{
if (f[i][p][0] && Ao + Bo + Da[i][p][0] + Db[i][p][0] <= X)
{
Ao += Da[i][p][0];
Bo += Db[i][p][0];
p = f[i][p][0];
}
}
}
这种解决方式也是 $LCA$ 的一个重要内容。
注意事项
$set$ 要插入两个极值
问题一的比值记得用浮点数保存。
总结
这道题是 NOIP2012 提高组 Day 1 压轴,实话实说,思维难度并不算高。
但代码实现细节很多,解决此题总用时 $3h$, 再接再厉吧!
如果城市只有一个 比值怎么输出呢
orz