An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.
Input
The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.
Output
For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.
Sample
| Inputcopy | Outputcopy1 |
|---|---|
|
|
一群蚂蚁在一根长为l厘米的水平杆上行走，每根杆子的恒定速度为1厘米/秒。当一只行走的蚂蚁到达杆子的尽头时，它会立即从杆子上掉下来。当两只蚂蚁相遇时，它们会回头并开始向相反的方向行走。我们知道蚂蚁在杆子上的原始位置，不幸的是，我们不知道蚂蚁行走的方向。你的任务是计算所有蚂蚁从杆子上掉下来所需的最早和最晚时间。
输入
输入的第一行包含一个整数，给出后面的事例数。每种情况的数据都以两个整数开头：杆子的长度（以厘米为单位）和n，即居住在杆子上的蚂蚁数量。这两个数字后面跟着n个整数，给出每只蚂蚁在杆子上的位置，作为从杆子左端测量的距离，没有特定的顺序。所有输入整数都不大于 1000000，并且用空格分隔。
输出
对于每种输入情况，输出两个由单个空格分隔的数字。第一个数字是所有蚂蚁从杆子上掉下来的最早时间（如果它们的行走方向选择得当），第二个数字是最晚的时间。
样本
| 输入复制 | 输出复制 |
|---|---|
|
|
解答：
实际上，这题的话，一开始可以很好的看出来，最短的时间怎么求，因为蚂蚁的速度都是一样的，所以当每只蚂蚁都向着距离自己端点更近的那个方向走，那么最后所消耗的时间是最短的，但是它消耗时间最长的有点迷惑性，它说蚂蚁碰头之后就会掉头走，实际上很迷惑，但是可以理解成蚂蚁碰头之后就擦肩而过（因为不是求走的路径，而是求时间），这样想了之后是不是解答起来就简单许多了呢？
下面是答案哦（本人ac的代码）
#include<iostream>
using namespace std;
const int N = 10 + 1e7;
int ans[N];
int main()
{
int n;
cin >> n;
while (n--)
{
int l, ant;
long long ans1=0;
long long a = 0;
long long b = 0;
long long ans2=0;
cin >> l >> ant;
for (int i = 0; i < ant; i++)
{
cin >> ans[i];
ans1 = min(ans[i], l - ans[i]);
a = max(ans1, a);
ans2 = max(ans[i], l - ans[i]);
b = max(ans2, b);
}
cout << a << " " << b << endl;
}
return 0;
}congratulations！