蚂蚁 算法之第二集

这是一个有趣的问题，题意不太容易理解，刚开始我就理解错了题意，原题如下：

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;
}
           

输入和结果如下：