快递机器人_图森未来笔试题

图森未来的员工阿伟最新研发了一款快递机器人，他投放了一台机器人在公司办公室中进行试运营。

公司的座位分布比较工整，可以看成一个四分之一平面上的网格图，即所有坐标轴上第一象限中的整点都是一个工位，上下左右相邻的工位间有一条长为1的边。由于阿伟资历比较深，所以坐在了公司的(1, 1)点上。

机器人每天都会从阿伟的座位出发，去n个同事的工位上收快递。每1秒中，机器人可以向x轴正方向，x轴负方向，或者y轴正方向移动1个单位（由于某些技术原因，暂时不允许向y轴负方向移动，同时也不允许移动到公司外，即不允许移动到x坐标小于等于0的位置）。例如，如果当前时刻机器人所在的坐标为(x, y)，下一秒机器人可能可以到达的位置为(x + 1, y)，(x - 1, y)或者(x, y + 1)。当机器人到达某个同事所在的工位时，就会获得要收取的快递，收快递的动作不需要消耗时间。一旦机器人收完所有快递，他就可以立即传送回仓库，把同事们的快递发送出去。

现在阿伟告诉了你今天需要去收快递的所有同事的工位坐标，他希望你可以写一个程序帮他计算一下收完所有快递最少所需要花费的总时间。

输入的第1行包含1个正整数n，表示当天要收货的同事数量。
接下来的n行，每行有两个正整数x和y，表示坐在(x, y)处的同事今天有快递需要收取。保证n个坐标两两不同。

对于 30% 的数据，1 <= n <= 8，1 <= x, y <= 1000；
对于另外 30% 的数据，1 <= n <= 1000，1 <= x, y <= 10⁶，并且保证没有任何超过8个同事位置的y坐标相同。
对于另外 40% 的数据，1 <= n <= 10⁵，1 <= x, y <= 10⁹；

快递机器人

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题