之前看有的朋友談百度的一道面試試題－
螞蟻問題（有一根27厘米的細(xì)木桿，在第3厘米、7厘米、11厘米、17厘米、23厘米這五個(gè)位置上各有一只螞蟻。木桿很細(xì)，不能同時(shí)通過一只螞蟻。開始時(shí)，螞蟻的頭朝左還是朝右是任意的，它們只會(huì)朝前走或調(diào)頭，但不會(huì)后退。當(dāng)任意兩只螞蟻碰頭時(shí)，兩只螞蟻會(huì)同時(shí)調(diào)頭朝反方向走。假設(shè)螞蟻們每秒鐘可以走一厘米的距離。編寫程序，求所有螞蟻都離開木桿的最小時(shí)間和最大時(shí)間）。關(guān)于這道題目，網(wǎng)上給出了很多的解釋，但從整體來看，基本都是用到了等價(jià)置換（等量代換）的思想。要求最小時(shí)間，即為“最不容易”先到達(dá)兩端的螞蟻以最短的時(shí)間到達(dá)，所以我們只需找到所有螞蟻中間的一只（共奇數(shù)只螞蟻）或兩只（共偶數(shù)只螞蟻）到達(dá)一端的最短時(shí)間。比較麻煩的是求最長時(shí)間，有人會(huì)覺得當(dāng)有很多只螞蟻時(shí)，中間的螞蟻們相互碰撞的次數(shù)多些會(huì)增加時(shí)間，感覺上比較復(fù)雜，可如果我們用等量代換的思想來解釋就比較容易。假設(shè)中間的任意兩只相鄰螞蟻即將發(fā)生碰撞，如：A －> <－B，當(dāng)A，B發(fā)生碰撞后，便有<－A B－>。A，B反向相當(dāng)于<－B A －> ，即二者繼續(xù)向著原來的方向前進(jìn)，對(duì)于任意相鄰的發(fā)生碰撞的螞蟻都適用，所以只需求最兩端的兩只螞蟻距離兩端的最遠(yuǎn)距離。由以上分析可知，如果出這樣的問題，我們可以不用通過程序便能說出結(jié)果：5個(gè)點(diǎn)，中間螞蟻的位置為11，即0－11－27，顯然最小為11，最兩端螞蟻，0－3－27，最大為24，0－23－27，最大為23，所以最大為24。對(duì)于這個(gè)題，給出如下Java代碼（隨便寫了幾句，不符合面向?qū)ο笏枷耄?br />
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("最短時(shí)間:"+min+" 最長時(shí)間:"+max);
}
}
有了如上的想法，我們能做出判斷，為什么還要寫代碼呢？其實(shí)這個(gè)問題出自Waterloo Local Contest Sep.19,2004 準(zhǔn)確描述如下：
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
在這里給出相應(yīng)的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;
}