蚂蚁爬行问题 · 算法程序设计

<table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">问题主题：Ants(POJ No.1852)</td></tr><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">问题描述：n只蚂蚁以每秒1cm的速度在长为Lcm的竹竿上爬行。当蚂蚁看到竿子的端点时就会落下来。由于竿子太细，两只蚂蚁相遇时，它们不能交错通过，只能各自反方向爬行。对于每只蚂蚁，我们只知道它离竿子最左端的距离为xi，但不知道它当前的朝向。请计算所有蚂蚁落下竿子的最短时间和最长时间。<img width="499" height="222" src="image/8be43a614ca632ec28e7e4e33048e613.jpg" alt=""/> 限制条件：1<=L<=1061<=n<=1060<=xi<=L</td></tr><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border-left-width:0.5pt; border-style:none solid solid; border-left-color:rgb(0,0,0); border-right-width:0.5pt; border-right-color:rgb(0,0,0); border-bottom-width:0.5pt; border-bottom-color:rgb(0,0,0)">样例：输入L=10n=3x={2,6,7}输出min=4{左、右、右}max=8{右、右、右}</td></tr></tbody></table> ### 【解法一】 ### 解题分析：对于最短时间，我们可以考虑当所有蚂蚁都向最近的端点移动时，这时不会发生两只蚂蚁相碰的情况，也就是时间最短的情况。对于最长时间，你也许会想蚂蚁有向左向右两种情况，相碰之后又向相反的方向移动，n只蚂蚁就有2n种可能,要考虑的情况就会特别多，而随n的增大急剧增加。但你仔细想一下两只蚂蚁相遇时的情况(如下图)会发现，由于相遇时相互反向移动且速度相同，我们可以认为是依原方向移动。如果你是高中生，一定会立马想到物理学中的动能定理…… ![](https://box.kancloud.cn/2016-08-24_57bd6c179761d.jpg) ### 程序实现: **C++** <table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">#include <iostream>#include <algorithm> const int L = 10;const int n = 3;const int x[n] = {2,6,7};int main() {int min, max;min = max = 0;int minX, maxX;for(int i=0; i<n; i++) {minX = x[i]<L-x[i]?x[i]:L-x[i];min = minX>=min?minX:min;maxX = x[i]>(L-x[i])?x[i]:L-x[i];max= maxX>max ? maxX : max;}cout<<min<<" "<<max<<endl;return 0;}</td></tr></tbody></table> **Java**** <table border="1" style="font-family:Simsun; border-collapse:collapse; padding:0pt 5.4pt"><tbody><tr><td width="568" valign="top" style="width:426.1pt; padding:0pt 5.4pt; border:0.5pt solid rgb(0,0,0)">package programdesign; public class Ants {public static void solve(int l, int x[]) {if(0 >= x.length)return;int min , max;min = max = 0;int d1, d2;for(int i=0; i<x.length; i++) {if(x[i]<=l-x[i]) {d1 = x[i];d2 = l-x[i];} else {d1 = l-x[i];d2 = x[i];}if(min < d1) {min = d1;}if(max < d2) {max = d2;}}System.out.println(min + " " + max);}public static void main(String[] args) {int x[] = {2,6,7};solve(10, x);} } </td></tr></tbody></table> **** ### 算法复杂度：时间复杂度O(n)