POJ 1852 Ants

题目描述：

　　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
思路分析：
　　这道题要求我们输出使所有蚂蚁全都掉下去的最小和最大的时间花费，最初我想：由于每只蚂蚁在不发生碰撞时的速度大小（不包括方向）都是相等的，那么我让他们都平行走，设杆长度为n，蚂蚁距最左端d，对每只蚂蚁的d和n-d取min，在输出最大值，则一定是最小的；而如果蚂蚁都往中间靠，由于最中间的蚂蚁被撞多次，在杆上做往复运动，那么它一定是耗时最大的，但我随手画的样例就不合适。

如图，我们设杆长为12,1号初始距离6,2号8,3号10，则当1s后，2,3相遇于距左端9处（图2），1在7处。之后第2s时，1,2相遇于距左端8处(图三)，之后三者不发生碰撞，但之后明显1号还需8s才可掉下，耗时最大，而它却不是中间的点，于是我们知道我们想错了。

于是我们假设有1,2两只蚂蚁，他们的距离为2，中间黑长直的是初始状态，那么两秒后，如果他们发生碰撞，则他们会变成上图情况，而我们如果让他们直接穿过彼此，就变成了下图。我们发现，上下图的两只蚂蚁只是编号不同，而他们彼此的速度大小，方向都相同，由于题目不要求计算编号，我们便可以把两只蚂蚁相碰简化为两只蚂蚁穿过彼此，他们的速度都不变，而大量蚂蚁相碰是由无数个一对蚂蚁相碰构成的，所以我们便可以像计算最小值一样从头到尾扫一遍，求出每只蚂蚁的d和n-d取max输出即可。

附上代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
const int Inf=0x3f3f3f3f;
int Min,Max;
int a[N];
int main(){
    //freopen("c.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        Min=-1,Max=-1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;++i){
            scanf("%d",&a[i]);
            Min=max(Min,min(a[i],n-a[i]));  //分别统计最大最小值 
            Max=max(Max,max(a[i],n-a[i]));
        }
        printf("%d %d
",Min,Max);
    }
    return 0;
}