题目链接-POJ1852   


Ants
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 15233   Accepted: 6610

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



题目大意：给你一根长度为L的水平杆（1-L cm）和n（n<=1e6）只蚂蚁的坐标，初始时每只蚂蚁的头朝的方向都不确定，蚂蚁移动的速度为 1cm/s 因为杆的宽度限制，当蚂蚁碰头时都要往反方向走，而当蚂蚁走到杆的端点时将会掉下去，问你当所有蚂蚁都已最快或最慢的时间掉下杆所有蚂蚁都掉下的时间！


题目思路：开始看到这个题目时没有啥思路，因为蚂蚁最初的方向都不确定，然后就去画图，因为考虑每只蚂蚁都选最近或最远的一端移动，如果前面的蚂蚁也和它是同一方向，就不需要考虑转向，而当前面的蚂蚁不是在同一方向时，碰撞你变成它要去的方向，你变成它要去的方向，这里如果想通了就很简单了，这时候相当于你和它相互交换，也就是它代替你走，你代替它走，因为你们之前走过的路程都已确定，交换后对之前状态也没有影响，到这里就不难想到了，每只蚂蚁最近的时间就是 min(x,L-x),最远的时间就是 max(x,L-x)  所以只需遍历一遍所有的蚂蚁的坐标即可，这个可以在输入时完成，时间复杂度为O(n)!


AC代码


#include<iostream>
#include<cstdio>
using namespace std;

#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
int main()
{
  int t;
  scanf("%d",&t);
  while(t--){
    int n,len;
    scanf("%d%d",&len,&n);
    int Min_ans=0,Max_ans=0;
    while(n--){
        int x;scanf("%d",&x);
        Min_ans=Max(Min_ans,Min(x,len-x));
        Max_ans=Max(Max_ans,Max(x,len-x));
    }
    printf("%d %d\n",Min_ans,Max_ans);

  }
  return 0;
}