【POJ】1852 - Ants（数学问题，思路）

Ants

Description

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 Input

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

Sample Output

4 8
38 207

Source

Waterloo local 2004.09.19

题意：一根竹竿上有若干蚂蚁，蚂蚁在竹竿任意一头都会掉下去，现在给你各个蚂蚁距离竹竿左边的距离，但是不知道蚂蚁的行进方向，若蚂蚁相遇则各自掉头往回走。

思路很不错啊。

最少时间能想到，就是所有蚂蚁所需要的最短时间（向左走向右走总有一个最短的时间），这些时间中取最大值就行了（保证所有蚂蚁都能掉下去）。

最长时间其实不难想，只是当时纠结到蚂蚁如何调头的问题上了，上午看题解想通了，其实蚂蚁相遇的时候不考虑调头的问题，就当没事发生一样，各走各的路，反正又不是问哪只蚂蚁最后掉下去，不必理会蚂蚁各自的方向，走就行了。

代码如下：

#include <cstdio>
int max (int a,int b)
{
	return a > b ? a : b;
}
int min (int a,int b)
{
	return a < b ? a : b;
}
int main()
{
	int u;
	int l,n;
	int ans_min,ans_max;
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%d %d",&l,&n);
		ans_min = -1;
		ans_max = -1; 
		for (int i = 1 ; i <= n ; i++)
		{
			int t;
			scanf ("%d",&t);
			ans_min = max (ans_min,min(t,l-t));
			ans_max = max (ans_max,max(t,l-t));
		}
		printf ("%d %d\n",ans_min,ans_max);
	}
	return 0;
}