螞蟻 算法之第二集

這是一個有趣的問題，題意不太容易了解，剛開始我就了解錯了題意，原題如下：

n隻螞蟻以每秒1cm的速度在長度為Lcm的杆子上爬行，當螞蟻爬到杆子的端點是就會掉落，由于杆子太細，每隻螞蟻相遇時，他們不能交錯通過，隻能各自反向爬回去，對于每隻螞蟻，我們知道它距離杆子左端的距離為xi，但不知道它目前的朝向，請計算所有螞蟻落下杆子所需要的最短時間和最長時間。

限制條件：

1=<L<=10^6

1=<n<=10^6

0=<xi<=L

結題思路：本題我一開始想到的是窮舉法，把所有的情況都組合起來，實作起來複雜，但不是不可以，書上給了一種很巧妙的方法，一般人不易想到，現在給大家介紹一下：

首先關于最短時間，所有的螞蟻都朝較近的端點走會比較好，相信大家都能想到，最長的時間比較難理想，螞蟻相遇以後，會相反方向運動，但我們可以假設他們交錯繼續前進（因為這裡的螞蟻速度是一樣的，要走的總路程是一定的，是以時間是一定的，仔細想一想),這樣就可以認為每個螞蟻都是獨立運動的，是以要求時間最長，最要求螞蟻到杆子的最大距離就行了。具體代碼如下：

#include <iostream>
#include<algorithm> 
using namespace std;
#define MAX_N 100
int _tmain(int argc, _TCHAR* argv[])
{
	int n, L, a[MAX_N];
	int minT = 0, maxT = 0;
	cout << "請輸入螞蟻數n,杆子的長度L,以及螞蟻到杆子左邊的距離a[i]:" << endl;
	cin >> n >> L;
	for (int i = 0; i < n; ++i){
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i){
		minT = max(minT,min(a[i], L-a[i]));
	}
	for (int i = 0; i < n; ++i){
		maxT = max(maxT, max(a[i],L-a[i]));
	}
	cout << "最短時間是%d: " << minT << endl;
	cout << "最長時間是%d: " << maxT << endl;
	return 0;
}
           

輸入和結果如下：