《重生学神有系统》第247章 对拍、Day1第三题

    没错，刚才的猜想是凭直觉和少量笔算搞出来的。
    要想验证自己的猜想，除了数学证明，最实用的方式就是对拍。
    所谓对拍程序，通俗的说法，就是数据比较器。
    方法很简单。
    将穷举暴力搜索版本的代码，编译成可执行文件a；
    将运用了猜想，优化后的代码编译成b；
    然后编写一个随机数据生成器，命名为rand；
    接下来，就可以制作对拍程序了。
    代码的主体是个有限次的循环。
    循环体内部，核心部分是几个system函数。
    先调用“./rand“生成随机数据，存入，再分别调用a、b，读取，输出和两个文本文件。
    最后调用““，进行比较。
    如果发现两个文本文件不一致，则说明优化后的程序有问题，于是提示错误信息以及出错原因。
    这就是对拍，号称最强的调试办法，比GDB之类的调试工具好用多了。
    江寒写完对拍之后，设了一个60000次的循环，花了2分多钟跑完一遍。
    结果没有输出任何错误信息，这表示自己的猜想是完全成立的。
    下一步，就该把优化后的代码扩展到高精度了。
    这一步对很多选手来说，都是个难点，很容易大意之下，写漏一些条件。
    比如位数的最大值处理得不好，或者犯下其他的小失误，就会导致运算出bug。
    倒也不一定完全不能运行，只是碰到特殊数据时，可能会得出不正确的输出。
    运气好的时候，也能正常得分，运气差一点，可能就会丢分了。
    高精度运算的基本原理，是模拟手工列竖式计算，其中要考虑数位对齐和进位、借位处理。
    这种代码在网上有的是，但运算效率上，那些比较常见的代码，就有点不敢恭维了。
    江寒在刷《NOIP宝典》的时候，自己研究出来了一种高精度算法，可以说是不传之秘，比网上能找到的示范代码，要精简和巧妙很多。
    在这道题里，江寒要做的就是模拟手算高精度乘除法。
    如果不打高精度，那么最多仅能满足40%的数据要求。
    这道题满分100，能看懂题目，并写出暴力搜索算法，就能20分。
    能发现规律，写出快速排序，就能得到40分。
    对于实力有限，有自知之明的选手，做到这里就可以收手了。
    只有那些对自己足够自信，且能熟练编写代码进行高精度运算的人，才会继续改造算法，以冲击高分。
    高精度的乘法好写，除法就稍微有点难度了。
    这里又有两种选择，一个是写高精除高精，满足100%的输入数据要求。
    要么就退而求其次，被除数为高精度，除数为单精度，这样也可以满足至少60%的输入数据要求。
    写对高精除以单精，能得60分，写出高精除以高精，才有机会得到满分。
    但高精除以高精，是相当复杂的，一旦写错、写漏了条件，说不定反而得不偿失，连60分都得不到。
    所以，是保证到手60分，还是冒着浪费时间的风险，冲击一下满分？
    对于其他人来说，这当然是个艰难的抉择，但对于江寒来说，根本无需纠结。
    反正时间也有的是，当然是选择后者了。
    江寒花了大约半个小时，写出了双高精除法的版本，并调试通过。
    然后设计了几组极限数值，代入进去运算，结果与笔算结果完全一致。
    边界条件没问题，这个程序出问题的几率就相当低了。
    倒也不是不能用系统作弊。
    做出爆搜程序后，可以通过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秒的运算时间。