蚂蚁算法之第二集算法

这是一个有趣的问题，题意不太容易理解，刚开始我就理解错了题意，原题如下：
n只蚂蚁以每秒1cm的速度在长度为Lcm的杆子上爬行，当蚂蚁爬到杆子的端点是就会掉落，由于杆子太细，每只蚂蚁相遇时，他们不能交错通过，只能各自反向爬回去，对于每只蚂蚁，我们知道它距离杆子左端的距离为xi，但不知道它当前的朝向，请计算所有蚂蚁落下杆子所需要的最短时间和最长时间。
【蚂蚁算法之第二集】限制条件：
1= 1= 0= 结题思路：本题我一开始想到的是穷举法，把所有的情况都组合起来，实现起来复杂，但不是不可以，书上给了一种很巧妙的方法，一般人不易想到，现在给大家介绍一下：
首先关于最短时间，所有的蚂蚁都朝较近的端点走会比较好，相信大家都能想到，最长的时间比较难理想，蚂蚁相遇以后，会相反方向运动，但我们可以假设他们交错继续前进（因为这里的蚂蚁速度是一样的，要走的总路程是一定的，所以时间是一定的，仔细想一想),这样就可以认为每个蚂蚁都是独立运动的，所以要求时间最长，最要求蚂蚁到杆子的最大距离就行了。具体代码如下：

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