[ACM] POJ 1852 Ants

Ants

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 7498		Accepted: 3457

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 <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int ant[1000003];

int main()
{
    int t,ti;
    int l,num;
    int i;
    cin>>t;
    for(ti=1;ti<=t;ti++)
    {
        cin>>l>>num;
        for(i=0;i<num;i++)
            scanf("%d",&ant[i]);
        int maxN=0,minN=0;
        for(int i=0;i<num;i++)
        {
            maxN=max(maxN,max(ant[i],l-ant[i])); //这两条很关键
            minN=max(minN,min(ant[i],l-ant[i]));
        }
        printf("%d %d
",minN,maxN);
    }
    return 0;
}

注意：大规模数据的时候记得用scanf printf 输入输出，否则会超时啊，切记！

运行截图：