|
题目描述 LYK在观察一些蚂蚁。 蚂蚁想要积攒一些货物来过冬。积攒货物的方法是这样的。 对于第i只蚂蚁，它要从li出发，拿起货物，走到ri处放下货物，需要消耗的时间为|ri-li|。而且所有蚂蚁都是可以同时进行的，也就是说，假如有m只蚂蚁，那么运输完货物的时间为max{|ri-li|}。 LYK决定帮蚂蚁一把，它发明了空间传输装置。具体地，当蚂蚁走到X处时，它可以不耗费任意时间的情况下瞬间到达Y，或者从Y到达X。也就是说，一个蚂蚁如果使用了空间传输装置，它耗费的时间将会是min{|li-X|+|ri-Y|,|li-Y|+|ri-X|}，当然蚂蚁也可以选择徒步走到目标点。 由于空间传输装置非常昂贵，LYK打算只建造这么一台机器。并且LYK想让蚂蚁运输完货物的时间尽可能短，你能帮帮它吗？
输入格式(ant.in) 第一行两个数n,m，n表示li,ri的最大值。 接下来m行，每行两个数li,ri。
输出格式(ant.out) 一个数表示答案
输入样例 5 2 1 3 2 4
输出样例 1
数据范围 对于20%的数据n,m<=100。 对于40%的数据n,m<=1000。 对于60%的数据n<=100000，m<=1000。 对于80%的数据n,m<=100000。 对于100%的数据n,m<=1000000，1<=li,ri<=n（li=ri时你甚至可以无视这只蚂蚁）。
样例解释 令空间传输装置的参数中X=2，Y=3或者X=3，Y=2都行。
| 
发表于 2021-10-29 09:38:31
收藏
楼主
