原文地址:
http://www.tkk7.com/dreamingnest/archive/2008/05/10/199672.html
之前看有的朋友談百度的一道面試試題－
螞蟻問題（有一根27厘米的細木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個位置上各有一只螞蟻。木桿很細，不能同時通過一只螞蟻。開始時，螞蟻的頭朝左還是朝右是任意的，它們只會朝前走或調頭，但不會后退。當任意兩只螞蟻碰頭時，兩只螞蟻會同時調頭朝反方向走。假設螞蟻們每秒鐘可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時間和最大時間）。關于這道題目，網上給出了很多的解釋，但從整體來看，基本都是用到了等價置換（等量代換）的思想。要求最小時間，即為“最不容易”先到達兩端的螞蟻以最短的時間到達，所以我們只需找到所有螞蟻中間的一只（共奇數只螞蟻）或兩只（共偶數只螞蟻）到達一端的最短時間。比較麻煩的是求最長時間，有人會覺得當有很多只螞蟻時，中間的螞蟻們相互碰撞的次數多些會增加時間，感覺上比較復雜，可如果我們用等量代換的思想來解釋就比較容易。假設中間的任意兩只相鄰螞蟻即將發生碰撞，如：A －> <－B，當A，B發生碰撞后，便有<－A B－>。A，B反向相當于<－B A －> ，即二者繼續向著原來的方向前進，對于任意相鄰的發生碰撞的螞蟻都適用，所以只需求最兩端的兩只螞蟻距離兩端的最遠距離。由以上分析可知，如果出這樣的問題，我們可以不用通過程序便能說出結果：5個點，中間螞蟻的位置為11，即0－11－27，顯然最小為11，最兩端螞蟻，0－3－27，最大為24，0－23－27，最大為23，所以最大為24。對于這個題，給出如下Java代碼（隨便寫了幾句，不符合面向對象思想）。
public class Ant 
{
public static void main(String[] args){
int length=27,points=5,min=0,max=0,temp_min=0,temp_max=0;
int[] pos={3,7,11,17,23};
for(int i: pos){
temp_min=i>length-i?length-i:i;
temp_max=i<length-i?length-i:i;
if(temp_min>min)
min=temp_min;
if(temp_max>max)
max=temp_max;
}
System.out.println("最短時間:"+min+" 最長時間:"+max);
}
}
有了如上的想法，我們能做出判斷，為什么還要寫代碼呢？其實這個問題出自Waterloo Local Contest Sep.19,2004 準確描述如下：
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.
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.
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
在這里給出相應的c++代碼：
#include<iostream>
using namespace std;
int main()
{
int cases,l,n,min,max,temp_min,temp_max,pos;
cin>>cases;
while(cases--)
{
cin>>l>>n;
min=0;
max=0;
while(n--)
{
cin>>pos;
temp_min=pos>l-pos?l-pos:pos;
temp_max=pos<l-pos?l-pos:pos;
if(temp_min>min)
min=temp_min;
if(temp_max>max)
max=temp_max;
}
cout<<min<<' '<<max<<endl;
}
return 0;
}