蓝桥杯 试题 历届试题 蚂蚁感冒
问题描述
长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; }
