3713: 电梯停靠(第二轮03)
题目描述
有一个 n 层高的楼， 电梯会在 1 ~ n 层之间运行。每次运行结束后， 电梯都会 自动停靠在 x 层。假设一个人想从第 5 层到第 10 层，那么电梯会先从第 x 层（因为之前已经自动停靠在 x 层了）走到第 5 层，然后从第 5 层走到第 10 层，最后再从第 10 层回到自动停靠的楼层 x 层。电梯总共会行走 |x − 5| + |5 − 10| + |10 − x | 的距离（其中 |x | 表示 x 的绝对值）
现在已知 m 个人依次乘坐电梯，每个人都会在电梯自动停靠在 x 层之后才乘 坐。第 i 个人乘坐电梯是从 a 层移动到 b 层。现在 x 由你设置，你需要让电 梯的总行走距离最短。请你输出对应的 x 和最短的行走距离。若有多个可能的 x，输出最小的一个。
输入
第一行包含两个正整数 n, m，表示楼的层数和乘坐电梯的人数。
接下来包含 m 行，每行给出两个数字 ai, bi (ai < bi )，意义如题面所示。
输出
输出两个数字，第一个数字表示电梯自动停靠的楼层，第二个数字表示电梯行走 的最短距离。
样例输入 复制
10 2
3 7
4 6样例输出 复制
4 12提示
【样例 1 输入】
10 2
3 7
4 6
【样例 1 输出】
4 12
【样例 1 说明】
电梯一开始自动停靠在位置 4，第一个人想要从第 3 层走到第 7 层。则电梯共 行走 |4 - 3| + |3 - 7| + |7 - 4| = 8。第二个人想要从第 4 层行走到第 6 层， 行走之后电梯停靠回第四层，电梯共行走 8 + |4 - 6| + |6 - 4| = 12。
若电梯自动停靠在 5 或 6，则总行走距离也是 12，但是对于多个可能的 x，应 该输出最小值。
【样例 2 输入】
15 4
3 7
2 6
10 13
1 5
【样例 2 输出】
5 40
【样例 3 输入】
15 7
1 2
1 2
1 2
8 9
10 11
12 13
14 15
【样例 3 输出】
8 74
【数据范围】
对于 20% 的数据，有 1 ≤ n, m ≤ 100
对于 50% 的数据，有 1 ≤ n, m ≤ 2000
对于另外 20% 的数据，对于任意的 i(1 ≤ i < m) 有 ai < bi < ai+1 < bi+1
对于 100% 的数据，有 1 ≤ n, m ≤ 5 ∗ 10^5 ， 1 ≤ a, b ≤ n