藍橋杯 試題 歷屆試題 螞蟻感冒
問題描述
長100厘米的細長直杆子上有n只螞蟻。它們的頭有的朝左，有的朝右。
每隻螞蟻都只能沿著杆子向前爬，速度是1厘米/秒。
當兩隻螞蟻碰面時，它們會同時掉頭往相反的方向爬行。
這些螞蟻中，有1隻螞蟻感冒了。並且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。
請你計算，當所有螞蟻都爬離杆子時，有多少只螞蟻患上了感冒。
輸入格式
第一行輸入一個整數n (1 < n < 50), 表示螞蟻的總數。
接著的一行是n個用空格分開的整數 Xi (-100 < Xi < 100), Xi的絕對值，表示螞蟻離開杆子左邊端點的距離。正值表示頭朝右，負值表示頭朝左，數據中不會出現0值，也不會出現兩隻螞蟻佔用同一位置。其中，第一個數據代表的螞蟻感冒了。
輸出格式
要求輸出1個整數，表示最後感冒螞蟻的數目。
樣例輸入
3
5 -2 8
5 -2 8
樣例輸出
1
樣例輸入
5
-10 8 -20 12 25
-10 8 -20 12 25
樣例輸出
3
這一題與 POJ No.1852(Ant）思路相似，首先來看一下POJ的題目：
題目描述：
因為題目難抄，所以直接用了//blog.csdn.net/qq_43751506/article/details/105836389這位朋友的圖片，我也是在一起來挑戰程式設計這本書中看到這一題的。
如果暴力搜索所有螞蟻向左或向右兩種可能，則有2^n複雜度，指數爆炸。
首先考慮最短時間：所有的螞蟻應該都朝向離自己近的一端爬行，即以左端為坐標0點，則[ 0, L/2 ] 的螞蟻應該朝左爬， (L/2, L ] 的螞蟻應該朝右爬。這時沒有螞蟻相遇的情況。
接下來思考最長時間。
如果直接考慮一個螞蟻不間斷的相遇，改變自己的方向…會讓問題變得很複雜。實際上，我們考慮的是最長時間，而不是某個螞蟻的狀態。
如果忽略了螞蟻之間的區別，可以認為兩個螞蟻相遇時是保持原方向交錯而過。
這樣思考問題就簡單多了：最長時間即螞蟻離端點的最遠距離。
主要程式碼：
//輸入 int n,L; int x[Max_N];//保存螞蟻的位置 void solve() { int Min_T = 0, Max_T = 0; for(int i=0; i<n; i++) { Min_T = max( Min_T, min(x[i],L-x[i])); //計算最短時間 Max_T = max( Max_T, max(x[i],L-x[i]));//計算最長時間 } printf("%d %d\n",Min_T,Max_T); }
在回頭看這道藍橋杯題：當螞蟻相遇時，同樣可以視為沒有改變方向交錯而過，只是和感冒的螞蟻相遇後另一隻也會感冒。
考慮兩種情況：
- 第一個數據為正值( 第一隻感冒的螞蟻頭朝右 )
首先看第一隻感冒的螞蟻的右端：因為我們考慮的是螞蟻相遇後仍按原方向移動，那麼對於第一隻感冒螞蟻右側方向也向右的螞蟻不會被感染( 畫×的螞蟻)
而右側方向向左的螞蟻會與第一隻螞蟻相遇而感冒。
之後再看左側：左側的螞蟻這時可能會被右側畫√的螞蟻感染。但左側方向也向左的不會被感染(速度相同，追不上)，只有左側方向向右的螞蟻會被感染。
- 再看第一個數據為負值（即第一隻感冒的螞蟻頭朝左）
首先看左側螞蟻，思路相同，左側方向向右的螞蟻最終會被感染，而向左的不會。
之後看右側，右側螞蟻可能會被左側畫√的螞蟻感染，但只有右側方向向左的。
綜合這兩張圖可以很發現：在第一隻感冒螞蟻左側方向向右的會被感染；右側方向向左的會被感染。所以程式碼就非常簡單。
實現程式碼：
#include<cstdio> //其實只要求在感冒位置左邊方向向右;右邊方向向左的個數就可以了 const int Max_N = 50; int n; int x[Max_N+1];// 0:沒有螞蟻 -1:向左 1:向右 int ant; //感冒螞蟻的位置 void solve() { int res = 0; for(int i=1; i<ant; i++){//左邊 向右 if( x[i]==1 ) res++; } for(int i=ant+1; i<=100; i++){//右邊 向左 if( x[i]==-1 ) res++; } printf("%d\n",res+1);//加上原來的第一隻感冒的螞蟻 } int main() { scanf("%d",&n); int a; scanf("%d",&a); ant = a>0 ? a : -a;//第一個位置是感冒的位置 while( --n ) {//剩下的n-1個 scanf("%d",&a); if( a>0 ) x[a] = 1;//向右 else x[-a] = -1; //向左 } solve(); return 0; }
