螞蟻爬行問題 · 算法程序設計

<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)