- 首页 > it技术 > >
问题描述：
n只蚂蚁以每秒1cm的速度在长为Lcm的竹竿上爬行。当蚂蚁看到竿子的端点时就会落下来。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反方向爬行。对于每只蚂蚁，我们只知道它离竿子最左端的距离为xi，但不知道它当前的朝向。请计算所有蚂蚁落下竿子的最短时间和最长时间。
解题分析：
【蚂蚁爬行问题】对于最短时间，我们可以考虑当所有蚂蚁都向（以中线为界）最近的端点移动时，这时不会发生两只蚂蚁相碰的情况，也就是时间最短的情况。
文章图片
对于最长时间，你也许会想蚂蚁有向左向右两种情况，相碰之后又向相反的方向移动，n只蚂蚁就有2n种可能,要考虑的情况就会特别多，而随n的增大急剧增加。但两只相同的蚂蚁相遇时，他们的位置是相同的，可以看成两只蚂蚁的移动方向没有发生改变（相当于蚂蚁一变成蚂蚁二，蚂蚁二变成蚂蚁一）没有由于相遇时相互反向移动且速度相同，我们可以认为是依原方向移动。
文章图片
代码：
#include
using namespace std;
//1.确定竿的长度、蚂蚁的个数、蚂蚁距离最左边的竿边的距离
//最短的时间：所有的蚂蚁都往距离较近的竿边爬行
//最长的时间：所有蚂蚁都往距离较远的竿边爬行
int main()
{
int length=10;
int n=3;
int num[]={2,6,7};
int maxx=0,minx=0;
//对于一只蚂蚁确定最长的爬行时间，最短的爬行时间
int max=0,min=0;
//通过每次与maxx.minx比较确定最后的时间
//最短的时间
for(int i=0;
imin?minx:min;
maxx=num[i]>length-num[i]?num[i]:length-num[i];
max=maxx>max?maxx:max;
}
cout<<"min_time: "<
推荐阅读
