蚂蚁感冒

why

一道关于数学的算法题

how

以第一只蚂蚁作为出发点，按照左右两边区间的形式来分析其他蚂蚁可能发生的所有情况

题目

一个木头上有很多蚂蚁，有一只蚂蚁必感冒，蚂蚁碰头就会调头，如果有一只感冒，在碰头的时候就会传染给另一只。输入n个蚂蚁，正数代表右方向，负数代表左方向，大小代表蚂蚁所在位置（具体左端点大小）。

分析一下

分析一

这里有一个理论基础，调头的我们不考虑方向，因为方向不影响蚂蚁的状态，我们把状态变了，具体是哪只蚂蚁调头了，并不影响结果，所以我们直接想象成，它改了状态然后接着走了，不调头。

分析二

第一只蚂蚁往右走【右区间】往左走，必然感染往右走，必然不会感染【左区间】往左走，必然不会感染往右走

如果右区间存在往左走的蚂蚁，必然会感染。如果右区间不存在往左走的，必然不会感染。

如果第一只蚂蚁往左走。。。。

解析成代码

计数左边向右走的，右边向左走的，都有可能是被感染蚂蚁。用大于号可以判断它的方向，和第一个数比大小可以知道该蚂蚁是在右区间还是左区间判定如果蚂蚁向右边走，并且右边区间没有向左走的蚂蚁。则感染数为1如果蚂蚁向左边走，并且左边区间没有向右走的蚂蚁，则感染数为1否则，感染数为【左边往右】走的，和【右边往左】走的总数注意：在代码中左区间往右走的，我们也计为感染，因为它虽然是有判定条件，但是仔细看会发现判定条件其实是依赖于右区间往左走的。所以不管我们怎么计数，最后我们只需要确定【右往左走】不为0，那么【左往右走】计数就是有效的。

import java.util.Scanner; public class AntInfection { static int[] nums; static int left; static int right; public static int checkCount() { for (int i = 1; i < nums.length; i++) { /*右区间往左走的*/ if (Math.abs(nums[i]) > Math.abs(nums[0]) && nums[i] < 0) { left++; } /*左区间往右走的*/ if (Math.abs(nums[i]) < Math.abs(nums[0])&& nums[i] > 0) { right++; } } if ((nums[0] > 0 && left==0)||(nums[0] < 0 && right == 0)) { return 1; }else{ return left+right+1; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numsLength = sc.nextInt(); nums = new int[numsLength]; for (int i = 0; i < numsLength; i++) { nums[i] = sc.nextInt(); } int result = checkCount(); System.out.println(result); } }

易错点在判定条件中比较大小的时候需要转换成绝对值比较。Math.abs( )

总结

左右 <—> 右左（左区间往右走，右区间往左走，他们的发生是存在依赖的）如果感染蚂蚁是左走，左右的为0，则感染数为1，如果感染蚂蚁是右走，右左的为0，则感染数为1其他情况，则左右右左都算数