华师一附中OI组

标题: 2764: 蚂蚁运输(ant) [打印本页]

作者: admin 时间: 2021-10-29 09:38
标题: 2764: 蚂蚁运输(ant)

题目描述

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

输出样例

数据范围

对于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都行。

作者: admin 时间: 2021-10-29 09:43
有没有感觉这个题和烘衣服有点相似？

欢迎光临华师一附中OI组 (http://hsyit.cn/)