標(biāo)題：螞蟻感冒

長100厘米的細(xì)長直桿子上有n只螞蟻。它們的頭有的朝左，有的朝右。

每只螞蟻都只能沿著桿子向前爬，速度是1厘米/秒。

當(dāng)兩只螞蟻碰面時，它們會同時掉頭往相反的方向爬行。

這些螞蟻中，有1只螞蟻感冒了。并且在和其它螞蟻碰面時，會把感冒傳染給碰到的螞蟻。

請你計算，當(dāng)所有螞蟻都爬離桿子時，有多少只螞蟻患上了感冒。

【數(shù)據(jù)格式】

第一行輸入一個整數(shù)n (1 < n < 50), 表示螞蟻的總數(shù)。

接著的一行是n個用空格分開的整數(shù) Xi (-100 < Xi < 100), Xi的絕對值，表示螞蟻離開桿子左邊端點的距離。正值表示頭朝右，負(fù)值表示頭朝左，數(shù)據(jù)中不會出現(xiàn)0值，也不會出現(xiàn)兩只螞蟻占用同一位置。其中，第一個數(shù)據(jù)代表的螞蟻感冒了。

要求輸出1個整數(shù)，表示最后感冒螞蟻的數(shù)目。

例如，輸入：
3
5 -2 8
程序應(yīng)輸出：
1

再例如，輸入：
5
-10 8 -20 12 25
程序應(yīng)輸出：
3

資源約定：
峰值內(nèi)存消耗 < 256M
CPU消耗 < 1000ms

請嚴(yán)格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標(biāo)準(zhǔn)，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include ， 不能通過工程設(shè)置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

Ideas

這道題一開始做的時候挺懵的，還想著用一個數(shù)組，然后不斷交換元素來模擬螞蟻爬桿的過程，但是發(fā)現(xiàn)太復(fù)雜了。

其實比較難操作是“當(dāng)兩只螞蟻碰面時，它們會同時掉頭往相反的方向爬行。”

其實可以看成穿越！

也就是說，雖然實際上它們是掉頭爬行了，但是我們模擬的時候其實可以看作是一只螞蟻穿過了另一只螞蟻。

如果能這么想的話，其實問題就很簡單了，我們只需要找到感冒的螞蟻，在它前進(jìn)的方向上，所有與它對著頭爬的螞蟻都會被感染，而在它爬行的相反方向，也就是它的背后，如果感冒螞蟻前方有被感染的螞蟻，所有跟它后面同一個方向爬的螞蟻都會被它往前爬的過程中感染的螞蟻感染。

當(dāng)感冒螞蟻往右爬時，所有在它前面的，即位置大于感冒螞蟻位置的，只要往左爬，即小于0，則會被感染，所有在它后面的，即位置小于感冒螞蟻位置的，只要往右爬，即大于0，則會被感染。

當(dāng)感冒螞蟻往左爬時，所有在它前面的，即位置小于感冒螞蟻位置的，只要往右爬，即大于0，則會被感染，所有在它后面的，即位置大于感冒螞蟻位置的，只要往左爬，即小于0，則會被感染。

可以發(fā)現(xiàn)，只要其它螞蟻的位置絕對值大于感冒螞蟻，且小于0，即會被感染，只要其它螞蟻的位置絕對值小于感冒螞蟻，且大于0，即會被感染。

OK，開始寫代碼。

Code

C++

#include <iostream> #include <cstdio> #include <cmath> using namespace std; int n; int main() {scanf("%d", &n);int pivot, left = 0, right = 0;scanf("%d", &pivot);for (int i = 1; i < n; i++){int x;scanf("%d", &x);//找到感冒螞蟻左邊邊且向右走的if (abs(x) < abs(pivot) && x > 0) right++;//找到感冒螞蟻右邊且向左走的if (abs(x) > abs(pivot) && x < 0) left++;}//特殊情況if ((pivot < 0 && right == 0) || pivot > 0 && left == 0) puts("1");else printf("%d\n", left + right + 1);return 0; }

C++代碼來源于AcWing
作者：Chengte
鏈接：https://www.acwing.com/solution/content/7077/

Python

if __name__ == '__main__':n = int(input())left, right = 0, 0nums = list(map(int, input().split()))for val in nums:if abs(val) > abs(nums[0]) and val < 0:right += 1if abs(val) < abs(nums[0]) and val > 0:left += 1if (nums[0] > 0 and right == 0) or (nums[0] < 0 and left == 0):print(1)else:print(left + right + 1)

在線評測：https://www.acwing.com/problem/content/description/1213/

總結(jié)

以上是生活随笔為你收集整理的2014年第五届蓝桥杯 - 省赛 - C/C++大学A组 - G. 蚂蚁感冒的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。