POJ 1852 Ants

POJ上的1852題，剛讀完題有一種云里霧里的感覺，尤其是每只螞蟻的運動方向不確定而且不能交錯通過，更讓人迷惑。
題目如下：
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

挑戰(zhàn)程序設(shè)計競賽中提到用暴力搜索和遞歸函數(shù)可以實現(xiàn)解題，但是隨著螞蟻數(shù)量的增加，搜索的時間也會急劇增加。所以選擇一個合適的算法才是最重要的。

首先思考最短時間，我們假設(shè)所有螞蟻都朝向更近的端點，這種情況下不會出現(xiàn)兩只螞蟻碰撞。最短時間即為使所有螞蟻都落下的時間。

其次是最長時間，我們先想象兩只螞蟻碰面再掉頭，然而如果認為兩只螞蟻沒有掉頭而是交錯通過也符合題意。所以，我們可以將每只螞蟻的運動都看作獨立運動，而最長時間也是螞蟻離桿子端點的最大距離。

所以有以下代碼：

#include<stdio.h>
#define maxn 100010

int a[maxn];
int l,n;
int max(int a,int b)                                 /*max函數(shù)返回最大值*/ 
{
   if(a>b)  return a;
   else  return b;

}
int min(int a,int b)                                 /*min函數(shù)返回最小值*/ 
{
    if(a<b) return a;
    else return b;
}
void solve()
{
    int minT=0,i;
    for(i=0;i<n;i++)                                /*遍歷每只螞蟻，求每只螞蟻的最小時間，并時刻更新minT*/ 
       minT=max(minT,min(a[i],l-a[i]));
    printf("%d ",minT);                             /*輸出最小時間，注意加空格*/ 

    int maxT=0;
    for(i=0;i<n;i++)                                /*遍歷每只螞蟻，求每只螞蟻的最大時間，并時刻更新maxT*/ 
       maxT=max(maxT,max(a[i],l-a[i]));
    printf("%d\n",maxT);                            /*輸出最大時間，注意要換行*/ 
}
int main()
{
    int t,i;
    scanf("%d",&t);                                 
    while(t--)
    {
        scanf("%d%d",&l,&n);
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);                       /*存儲每只螞蟻離左端點的距離*/ 
        solve();                                     /*調(diào)用solve函數(shù)*/ 
    }
    return 0;
}

該算法時間復(fù)雜度O(n)，對于10^6足夠了，運行通過。

本題最大的驚喜應(yīng)該是對于選手思維上的挑戰(zhàn)和啟發(fā)，將螞蟻間相遇的情況考慮清楚后，借助一個循環(huán)就能輕松解決問題。實際上也不用考慮最長時間和最短時間問題，借助max和min函數(shù)即可解決問題。