第247章 对拍、Day1第三题

怕用最笨拙的办法，写个暴力搜索程序，都能保底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都可以。

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

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