M01852: Ants

physics, greedy , http://cs101.openjudge.cn/practice/01852

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.

输入

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.

输出

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.

样例输入

2
10 3
2 6 7
214 7
11 12 7 13 176 23 191

样例输出

4 8
38 207

来源：Waterloo local 2004.09.19

秋叶拓哉等人（秋叶拓哉，岩田阳一，北川宜稔. 挑战程序设计竞赛（第2版）[M]. 巫泽俊，庄俊元，李津羽，译. 北京：人民邮电出版社，2013.7.）的解题思路：解题思路：首先很容易想到一个穷竭搜索算法，即枚举所有蚂蚁的初始朝向的组合，这可以利用递归函数实现。每只蚂蚁的初始朝向都有2种可能，n只蚂蚁就是2 x 2 x … x 2=2^n^ 种。如果n比较小，这个算法还是可行的，但指数函数随着n的增长会急剧增长。 2^n^增长的趋势
n 1 5 10 20 30 100 10000 1000000
2^n^ 2 32 1024 1048576 10^9^ 10^30^ 10^3010^ 10^301030^
穷竭搜索的运行时间也随之急剧增长。一般把指数阶的运行时间叫做指数时间。指数时间的算法无法处理稍大规模的输入。接下来，让我们来考虑比穷竭搜索更高效的算法。首先对于最短时间，看起来所有蚂蚁都朝向较近的端点走会比较好。事实上，这种情况下不会发生两只蚂蚁相遇的情况，而且也不可能在比此更短的时间内走到竿子的端点。接下来，为了思考最长时间的情况，让我们看看蚂蚁相遇时会发生什么。
事实上，可以知道两只蚂蚁相遇后，当它们保持原样交错而过继续前进也不会有任何问题，因为所有蚂蚁是同时出发的。这样看来，可以认为每只蚂蚁都是独立运动的，所以要求最长时间，只要求蚂蚁到竿子端点的最大距离就好了。这样，不论最长时间还是最短时间，都只要对每只蚂蚁检查一次就好了，这是O(n)时间的算法。对于限制条件n≤ 10^6^, 这个算法是够用的，于是问题得解。

n	1	5	10	20	30	100	10000	1000000
2^n^	2	32	1024	1048576	10^9^	10^30^	10^3010^	10^301030^

小蚂蚁相遇后各自改变方向，可以看作错身而过，没有区别。

python

t = int(input())
for _ in range(t):
    L,n = map(int, input().split())
    x = map(int, input().split())
    minT = maxT = 0
    for i in x:
        minT = max(minT, min(i, L-i))
        maxT = max(maxT, max(i, L-i))
    
    print(minT, maxT)

M01852: Ants ​

M01852: Ants