做出爆搜程序后，可以通过20%的校验点，系统就提示了一次获得“学以致用”积分。

    运用了猜想，改为快速排序后，系统再次提示，获得了“学以致用”积分。

    改成高精度后，系统也有获得更多积分的提示。

    这说明，江寒对程序做出的每次改进，都能使其通过更多的校验点。

    但系统的帮助也只能到这里了，只能据此判断出，每个步骤中的程序，都是可以得分的，却无法判断出是否能得到满分。

    江寒只能依靠自己丰富的编程经验，尽可能保证程序无bug。

    搞定了前两道题后，时间已经过去了1个半小时。

    剩下的两个小时，全部交给最难的第三题。

    题目是《开车旅行》。

    题目概述：将n个城市编号为1~n，编号小的城市在编号较大的城市之西。

    各个城市海拔都不一样，城市i的海拔为hi，城市i与j之间的距离d为两城市海拔之差的绝对值。

    也就是说d=|hi-hj|。

    a、b二人轮流开车，从a开始，每日轮换。

    选择一个城市s为起点，一直向东，最多行驶x公里，就结束。

    a、b驾驶风格不同，b总是沿着前进方向，选择最近的城市作为目的地，a总是沿着前进方向，选择第二近的城市作为目的地。

    ps：如果两个城市距离相同，则海拔低的视为较近。

    如果其中任何一人，无法按照自己的原则选出目的地，或者到达目的地会使公里总数超过x，就结束旅行。

    输入文件中包含如下内容：城市n的数目，城市1~n的海拔高度，x0，m组si和xi。

    输出文件中，要求回答两个问题。

    1、对于给定的x=x0，从哪一个城市出发，a开车行驶的路程与b开车行驶的路程比值最小？

    2、对于任意给定的x=xi和出发城市si，a、b开车行驶的路程总数是多少？

    说实话，这道题的难点，主要在于题目的表述比较复杂。

    一般人光看懂题目，就至少需要15分钟……

    江寒也足足花了5分钟，才搞清楚题目的意思。

    但如果让他评价这道题的难度……

    勉强3星吧。

    这个题目的简单之处在于，哪怕用最笨拙的办法，写个暴力搜索程序，都能保底70分。

    可以说是白给。

    但如果想拿满分，难度直接飙升到天际。

    毕竟题目中规定：对于100%的数据，有1≤n≤100，000，1≤m≤10，000；

    -1，000，000，000≤hi≤1，000，000，000；

    0≤x0≤1，000，000，000；

    1≤si≤n；

    0≤xi≤1，000，000，000。

    其中，数据保证hi互不相同。

    江寒很想吐槽，海拔的上限是10亿，这么高的地方，肯定不在地球上吧？

    而海拔的下限-10亿，这已经low穿地心了喂！

    好吧，又是一个“艰难”的选择，到底是稳定拿70分，还是冒着巨大的风险，冲击更高的分数？

    这道题的关键仍然是数据预处理。

    预处理得好，直接难度减半。

    关于预处理，有很多可行的办法，离散化链表、双向链表、平衡树……

    甚至stl的set都可以。

    但不能用复杂度为o的算法，那样很容易在校验时，时间超限。

    毕竟根据规定，每个校验点只有1秒的运算时间。